[알고리즘] 깊이 우선 탐색(DFS)

DFS란?

 

깊이 우선 탐색으로 그래프 완전 탐색 기법중 하나로 탐색할 분기를 하나 정해 최대 깊이 까지 탐색을 마친 후 다른 분기로 이동하여 다시 탐색을 수행하는 알고리즘이다.

 

DFS는 스택 이나 재귀 함수 구조로 구현한다.

 

DFS는 한번 방문한 노드를 다시 방문하면 안되므로 노드 방문 여부를 체크하는 배열이 필요하다.

 

DFS 탐색 하기

- 탐색은 재귀 함수 구조로 탐색해보려 한다.

 

0번부터 5번까지 노드와 간선이 존재하는 그래프이다. 이 그래프를 표로 표현해보면

노드(V)	연결된 노드
0	2	4	5
1	4	5
2	0	3	4
3	2
4	0	1	2	5
5	0	1	4

 

- 0번 노드는 2번, 4번, 5번 노드와 연결되어 있다.

- 1번 노드는 4번, 5번 노드와 연결되어 있다.

- 2번 노드는 0번, 4번 노드와 연결되어 있다.

- 3번 노드는 2번 노드와 연결되어 있다.

- 4번 노드는 0번, 1번, 2번, 5번 노드와 연결 되어 있다.

- 5번 노드는 0번, 1번, 4번 노드와 연결되어 있다.

 

아직 탐색을 시작하지 않았으므로 방문 여부 배열은 아래와 같이 모두 False이다.

노드	0	1	2	3	4	5
방문 여부	F	F	F	F	F	F

 

1. 0번 노드부터 탐색

 

0번 노드부터 탐색을 시작하면  0번 노드는 방문을 시작 했으므로 True로 바뀐다.

노드	0	1	2	3	4	5
방문 여부	T	F	F	F	F	F

 

탐색한 0번 노드와 인접한 노드는 2번, 4번, 5번 노드이다. 보기 편하게 다음으로 2번 노드를 방문해준다.

 

2. 2번 노드 탐색

2번 노드를 탐색 했으니 방문 배열에 True로 체크 해준다. 한쪽 분기로 최대 깊이 까지 탐색하므로 4번, 5번 노드는 잠시 둔다.

노드	0	1	2	3	4	5
방문 여부	T	F	T	F	F	F

 

최대 깊이까지 가야하므로 2번 노드의 인접 노드를 확인해본다.

2번 노드와의 인접노드는 0번, 3번, 4번 노드이다. 0번 노드는 맨 처음 방문해서 True로 체크가 되어 있으므로 방문하지 않은 노드는 3번 노드와 4번 노드가 있다.  3번과 4번 어느 노드로 가도 상관은 없지만 보기 편하게 3번 노드 먼저 방문을 해본다.

 

3. 3번 노드 탐색

3번 노드를 탐색 했으므로 마찬 가지로 3번 노드도 True로 체크해준다.

노드	0	1	2	3	4	5
방문 여부	T	F	T	T	F	F

 

위에서의 방식과 마찬가지로 3번 노드의 인접 노드도 찾아본다.

3번 노드와의 인접 노드는 2번 노드이다. 하지만 방문 배열을 봐보면 2번 노드는 이미 방문 했다고 체크가 되어 있다.

따라서 현재 분기에서 최대 깊이까지 탐색이 되었으므로 다시 위로 돌아간다.

3번 노드에서 다시 돌아가보면 2번 노드로 돌아오게 되고 2번 노드의 인접 노드 3번, 4번 중 탐색하지 않은 4번 노드를 탐색하기 시작한다.

 

4. 4번 노드 탐색

4번 노드를 방문 했으므로 4번 노드의 방문 여부를 True로 체크해준다.

노드	0	1	2	3	4	5
방문 여부	T	F	T	T	T	F

 

4번 노드의 인접 노드를 살펴 보면 0번, 1번, 2번, 5번 노드와 인접해 있다. 이중에서 방문 하지 않은 노드는 1번과 5번 노드로 보기 쉽게 1번 노드 먼저 방문해준다.

 

5. 1번 노드 탐색

1번 노드를 방문 했으므로 1번 노드의 방문 여부를 True로 체크한다.

노드	0	1	2	3	4	5
방문 여부	T	T	T	T	T	F

 

1번 노드의 인접 노드를 살펴보면 4번, 5번 노드가 있고 이중에서 방문하지 않은 노드는 5번 노드이므로 5번 노드를 방문한다.

 

6. 5번 노드 탐색

5번 노드를 방문 했으므로 5번 노드의 방문여부를 True로 체크한다.

노드	0	1	2	3	4	5
방문 여부	T	T	T	T	T	T

 

5번 노드의 인접 노드를 살펴보면 0번, 1번, 4번 노드인데 이 노드들은 모두 탐색이 되어 있다. 이쪽 분기도 탐색이 끝났으므로 

다시 4번 노드로 돌아가서 남은 노드였던 5번 노드를 방문하면 되는데 이미 5번 노드는 방문되어 있어서 다시 0번 노드로 돌아오게 되는데  0번 노드에서 처음 2번 노드를 방문하고 방문하지 않았던 4번 5번 노드를 가려 했지만 4번 , 5번 노드도 탐색을 하면서 이미 방문을 했으므로 탐색이 종료된다.

 

탐색 순서를 보면 0 - 2 - 3 - 4 - 1 - 5가 된다.

 

시작 노드를 무슨 노드로 하냐에 따라서 탐색 순서는 바뀔 수가 있다.

 

 

DFS 마무리

DFS의 핵심은 한번 방문한 노드를 다시 방문 하지 않는다는 것이고 한쪽 분기의 최대 깊이까지 내려가는 것이다.