유진's 공부로그

문제 설명 m x n 크기인 사무실이 있습니다. 사무실에는 전염병에 걸린 직원이 있는데, 이 직원은 매일 상하좌우로 병을 퍼트려 다른 직원을 감염시킵니다. 단, 백신을 접종한 직원은 면역력이 있어 감염되지 않습니다. 예를 들어 2x4 크기 사무실에서, 병에 걸린 직원의 위치가 (1,4), (2,2)이고 백신을 맞은 직원의 위치가 (1,2)입니다. 이때 백신을 맞은 직원을 제외한 모든 직원이 병에 감염되기 까지는 이틀이 소요됩니다. 사무실의 크기 m, n과 병에 걸린 직원의 위치 infests, 백신을 맞은 직원의 위치 vaccinateds가 매개변수로 주어집니다. 이때 백신을 맞은 직원을 제외한 모든 직원이 병에 감염되기까지 며칠이 걸리는지 return 하는 solution 함수를 완성해주세요. 제한 사..

FloodFill과 그래프 탐색 floodfill 같은 경우엔 주어진 시작점으로부터 연결된 영역의 크기를 구하는 문제이다. (하나의 알고리즘으로 분류되는 듯하다) 프로그래머스 스터디에 참가하면서 floodfill 이라는 문제를 오래 붙잡고 있었는데, 이런 문제는 쉽게 접근하자면 모든 점마다 bfs, dfs를 수행하면서 영역 별로 "조져주는" 것이 해결책임을 알아냈다! 한 번의 탐색만으로는 수행이 불가능하다. (모든 정점을 한 번씩만 방문하는 걸로는 해결이 안된다는 의미) 처음에는 dfs 풀이만을 생각해냈는데, 한 번의 dfs만으로 풀이하려 했기에 해당 풀이도 오류가 떴다 (당시엔 몰랐음 ㅎㅎ... 컴퓨터는 죄가 없다. 코드를 짜는 나에게 있다 죄는 ^^). bfs로는 도저히 어떻게 푸는 건지 감이 안와서..

DFS(Depth-First Search; 깊이우선탐색)와 BFS(Breadth-First Search; 너비우선탐색)는 그래프의 정점을 방문하는 그래프 탐색(Graph Search or Graph traversal; 그래프 운행) 방법의 큰 갈래이다. 코딩 테스트 시에는 DFS를 좀 더 많이 활용하는 듯하다. DFS는 스택이나 재귀로, BFS는 큐로 구현한다. python에서 그래프는 아래와 같이 보통 딕셔너리를 활용해서 인접 리스트로 구현하는 경우가 많다. graph = { 1: [2,3,4], 2: [5], 3: [5], 4: [], ... } DFS (깊이 우선 탐색) 일단 임의의 한쪽 방향으로 갈 수 있을 때까지 가다가 더 이상 갈 수 없게 되면 가장 가까운 갈림길로 돌아와서 그곳으로부터 다른 ..