안녕하세요 오늘은 DFS의 문제 유형을 분석해보는 시간을 갖도록 하겠습니다. DFS 문제를 풀 때 고려해야 할 사항은 모든 그래프가 연결되어 있지 않을 수 있는 경우입니다. DFS는 하나의 노드에서 깊게 탐색하는 방식이다 보니 전체 탐색을 위해선 탐색 위치를 반복문을 통해 조율해야 합니다. 반면 BFS의 경우 하나의 시작점에서 인접한 그래프로 한 칸씩 이동하면서 체크하며 초기 위치가 보통 정해져 있습니다. 따라서 DFS는 모든 그래프가 연결되어 있지 않을 수 있는 경우가 존재하는 그래프에서 BFS 대신 사용됩니다.
첫 번째 유형은 그룹 또는 묶음의 수를 구하는 문제입니다. 이 문제 유형은 세부적으로 두 가지로 나뉩니다. 첫 번째는 인접 행렬(ex map[][])을 주고 내부에서 그룹핑한 그룹의 수를 구하는 문제, 두 번째는 인접 그래프(ex ArrayList<>[])를 주고 내부에서 그룹핑한 그룹의 수를 구하는 문제입니다. 두 경우 같은 방식으로 dfs를 이용하여 행렬 또는 그래프 전체를 탐색하면서 dfs를 진행한 횟수를 출력합니다.
백준 2667(단지 번호 붙이기) 문제의 경우 총 단지 수를 출력하는 문제입니다. 같은 묶음끼리 같은 단지이기 때문에 인접 행렬을 탐색하여 각 지점 별로 dfs를 진행하여 총 dfs를 진행한 횟수를 출력합니다.
백준 1012(유기농 배추) 문제의 경우 필요한 최소 지렁이 수를 구하는 문제입니다. 배추 그룹에 1개의 지렁이가 필요하므로 인접 행렬을 탐색하여 각 지점 별로 dfs를 진행하여 총 dfs를 진행한 횟수를 출력합니다.
백준 11724(연결 요소의 개수) 문제의 경우 방향 없는 그래프의 연결 요소의 개수를 구하는 문제입니다. 서로 연결되어 있는 노드의 그룹 개수를 구하는 문제이기 때문에 인접 리스트를 탐색하여 각 지점 별로 dfs를 진행하여 총 dfs를 진행한 횟수를 출력합니다.
백준 10026(적록 색약) 문제의 경우 적록색약이 봤을 때와 아닌 사람이 봤을 때의 구역의 수를 구하는 문제입니다. 적록 색약의 경우 R과 G를 같은 값으로 보고 dfs를 진행하고, 일반 사람의 경우 그대로 dfs를 진행하여 각각 dfs를 진행한 횟수를 출력합니다.
백준 2468(안전 영역) 문제의 경우 장마철 물에 잠기지 않는 안전한 영역의 최대 개수를 구하는 문제입니다. 비의 양을 증가시키면서 인접 행렬에서 현재 비의 양보다 큰 값만을 탐색하면서 총 dfs를 진행한 횟수의 최댓값을 출력합니다.
백준 2573(빙산) 문제의 경우 빙산이 두 덩이 이상으로 분리되는 최초의 시간을 구하는 문제입니다. dfs로 빙산 덩어리 개수를 센 후 한 덩어리일 경우 자신의 옆이 바다인 경우를 세어 "한번에' 빙산 카운트를 줄여야 합니다. 만약 그때그때 빙산 카운트를 줄이게 된다면 줄인 후 다음 빙산에서 카운트를 할 때 이전 카운트가 줄어듦에 따라 바다로 바뀐 부분까지 카운트가 되기 때문에 잘못 세어질 가능성이 존재합니다.
두 번재 유형은 그룹 내의 요소의 개수 또는 그룹의 크기를 구하는 문제입니다. dfs 특성 한 하나의 그룹을 끝까지 탐색하기 때문에 한 번의 dfs 연산으로 그룹의 모든 노드를 방문할 수 있습니다. 따라서 그룹 내의 요소의 개수 또는 그룹의 크기를 구할 때 적합합니다.
백준 1743(음식물 피하기) 문제의 경우 제일 큰 음식물의 크기를 출력하는 문제입니다. 인접한 음식물끼리 같은 덩어리이기 때문에 인접 행렬을 탐색하여 각 지점 별로 dfs를 진행하여 가장 많이 탐색한 횟수를 출력합니다.
백준 2606(바이러스) 문제의 경우 1번 컴퓨터를 통해 바이러스가 걸리게 되는 컴퓨터 수를 구하는 문제입니다. 1번과 연결되어 있는 노드의 개수를 구하는 문제이므로 인접 리스트를 생성 후 1번에서 dfs를 진행했을 때 탐색한 노드의 개수를 출력합니다.
백준 2583(영역 구하기) 문제의 경우 직사각형으로 분리된 영역의 개수 및 넓이를 구하는 문제입니다. 직사각형 부분을 탐색하지 않고 인접 행렬을 탐색하여 각 지점별로 dfs를 진행하여 총 dfs를 진행한 횟수와 dfs를 진행 시 탐색한 노드의 개수를 모두 출력합니다.
백준 1520(내리막길) 문제의 경우 제일 왼쪽 위 지점에서 제일 오른쪽 아래까지 항상 내리막길로만 이동하는 경로의 개수를 구하는 문제입니다. 왼쪽 위에서 자기보다 작은 값만 dfs로 탐색하여 도착 지점까지 도달했을 경우 정답을 1씩 증가시키는 방법으로 문제를 풀어나갑니다. 여기서 주의할 점은 일반적으로 탐색하게 되면 시간 초과가 발생하기 때문에 dp를 이용하여 현재까지의 경로의 개수를 저장하여 해당 값이 존재하면 dp값을 리턴하는 식으로 연산을 줄일 수 있습니다.
백준 1937(욕심쟁이 판다) 문제의 경우 이동한 지역보다 대나무가 많이 있도록 최대한 많은 칸을 이동 가능한 횟수를 구하는 문제입니다. 매 순간마다 인접 행렬을 저장해야 하기 때문에 메모리를 할당하지 않는 dfs 방식으로 진행하며(맵으로 현재 데이터를 저장하는 방법도 가능할 것 같은데 조금 더 확인해보겠습니다), 시간 초과를 방지하기 위해 dp를 이용하여 이미 계산한 결과를 저장하여 연산을 최소화하는 방식으로 값을 출력합니다.
백준 1707(이분 그래프) 문제의 경우 그래프가 이분 그래프인지 판별하는 프로그램을 작성하는 문제입니다. 이분 그래프의 특성상 인접한 노드들이 같은 그룹을 가지면 안되기 때문에 탐색을 하면서 인접 노드의 그룹을 현재 노드와 다르게 처리합니다. 이 때 주의할 점은 그래프의 모든 노드가 이어져 있지 않을 수 있기 때문에 BFS 대신 DFS로 처리하며, 방문한 노드가 같은 그룹에 존재할 경우 이분 그래프가 아니기 때문에 정답을 false 처리하는 방식으로 풀 수 있습니다.
