DFS(깊이우선탐색, 백준 알고리즘 4963번)

♣ DFS(Depth-First-Search, 깊이우선탐색)

트리나 그래프를 탐색하는 기법 중 하나로, 시작 노드에서 자식의 노드들을 순서대로 탐색하면서 깊이를 우선으로 탐색하는 알고리즘을 의미한다. 깊이를 우선시하여 모든 경우의 수를 탐색하며, 주로 반복문이나 재귀문을 활용하여 구현한다. 

 

♣ DFS 탐색과정

 

1. 현재 노드를 방문한 것으로 표시함

2. 방문 표시가 되어 있지 않은 각각의 인접한 정점을 탐색함

3. 더 이상 방문하지 않은 정점이 없으면 이전 정점으로 역추적(backtracking)함

4. 모든 정점을 방문할 때까지 과정을 반복함

 

0번 노드에서 탐색을 시작하면서 자식 노드인 1과 2를 탐색할 수 있다. 

1번 노드를 탐색하였다고 결정하면 1번 노드의 자식들까지 완벽하게 탐색하기 전까지 2번 노드는 탐색하지 않는다. 

1번 노드에는 자식 노드 3, 4가 있는데 3번 노드를 완벽히 탐색하기 전까지 4번 노드는 탐색하지 않는다. 

3번 노드의 자식인 7번 노드까지 탐색하고, 탐색이 완료되면 탐색 완료 표시를 한 뒤 3번 노드로 되돌아간다. 

3번 노드 역시 탐색이 끝났기 때문에 탐색 완료 표시를 한 뒤 1번 노드로 돌아간다. 

이후에 아직 탐색하지 않은 자식 노드인 4번 노드를 탐색한다. 

 

이러한 과정을 거치면 모든 노드를 탐색할 수 있다. 

 

♣ DFS의 특성

1. 목표가 특정한 정점, 또는 모든 정점에 최대한 빨리 도달하는 것일 때 유용하다.

2. 순환 그래프의 경우, DFS가 무한 루프에 빠질 수 있다. 

 

♣ 문제 이해

 

 

 

 

 

위의 문제는 섬의 개수를 세는 것이 목적이다. 가로, 세로, 대각선 방향으로 서로 건너갈 수 있으면 같은 섬이므로 검은 칸의 수를 모두 세는 것이 아니라 건너가는 것까지 포함해서 섬의 개수를 세야 한다. 위 예제에서는 섬이 총 3개인 셈이다. 

 

이 문제를 해결하는 데 DFS를 적용할 수 있다. 처음에 시작하는 섬 칸을 루트 노드라고 생각하고 연결되어 있는 모든 자식 노드를 탐색하여 한 개의 섬으로 체크하는 것이다. 

 

 

♣ 코드

 

시간 초과 없이 재귀함수를 사용하기 위해 sys.setrecursionlimit을 넣었다. 

 

 

while문은 주어진 수를 이용하여 field를 만들기 위해 사용했다. 이 문제에서는 테스트 케이스가 몇 개인지를 알려주지 않고, 입력의 마지막 줄에 0이 두 개 주어지면 끝을 내야 한다. 따라서 w, h로 지도의 너비와 높이를 구하되, 둘 다 0이면 while문을 종료하도록 했다. count는 섬의 수를 의미한다. field는 지도 전체에 우선 0을 넣어서 구성한다. 

 

그 후 for문을 이용하여 field를 채운다. h 줄만큼 주어지는 입력을 받아서 field[y][x]에 하나씩 넣었다. 

 

field를 채우고 나면 땅은 1, 바다는 0이다. 이제 field의 모든 칸을 돌면서 해당 칸이 1인 경우에 깊이우선탐색을 실시하여 인접한 1인 칸들을 모두 알아내면 된다. 이중 for문을 써서 field의 모든 칸을 탐색하되, 해당 칸이 1이면 우선탐색을 실시해서 인접한 칸들까지 탐색하도록 했다. 인접한 칸들을 자식 노드처럼 생각하고 탐색하는 것이다. 해당 칸에 대한 깊이우선탐색이 끝나면 count에 1을 더한다. 깊이우선탐색이 종료되었다는 것은 그 칸과 인접한 칸, 모든 자식 노드들에 대한 탐색이 끝났다는 것을 의미한다. 

 

위의 코드에서 사용한 dfs 함수이다. 위의 field[y][x] == 1일 때, 이와 인접한 칸들을 탐색하는 함수이다. 

 

x, y가 각각 0, 0 의 위치라고 생각하면 인접한 칸들의 위치는 다음과 같다. 

인접한 칸들을 탐색하기 위해 x_range와 y_range 범위를 정하고, field의 y, x 값을 바꿔가면서 인접한 칸들을 모두 방문하여 탐색한다. 그리고 인접한 칸 중 주어진 숫자가 1인 칸이 있으면 그 칸과 인접한 칸들(트리로 치면 자식 노드들)을 탐색해야 하므로 재귀함수를 또 다시 실행한다. 

 

 

전체코드

 

field를 만드는 과정부터 설명하기 위해 while문을 먼저 이야기했지만 재귀함수를 while문 앞에 먼저 정의하였다. 

 

♣ 참고 자료

DFS

https://olrlobt.tistory.com/35

[알고리즘] DFS (Depth-First Search) : 깊이 우선 탐색 알고리즘이란?