깊이 우선 탐색(DFS: Depth First Search)

트리나 그래프를 탐색하는 방법엔 여러가지가 있습니다. 그 중 가장 보편적인 방법이 깊이 우선 탐색과 너비 우선 탐색입니다.

이번에는 두 가지 탐색 방법 중 깊이 우선 탐색에 대해 알아보겠습니다.

깊이 우선 탐색에 대해 말해보자면 말 그대로 깊숙이 탐색하는 방법입니다. 예를 들어서 살펴보겠습니다.

---

[예시 그래프]

깊이 우선 탐색 알고리즘은 간단하게,

 1. 노드와 연결된 탐색하지 않은 이웃 노드 중 하나를 탐색한다.
 2. 탐색하지 않은 이웃 노드가 없는 경우 이전 노드로 돌아간다.
 3. 1번으로 돌아간다.
입니다. 이를 모든 노드가 탐색될 때까지 실행합니다.

위의 그래프를 1번 노드 부터 깊이 우선 탐색(DFS)으로 탐색해 보겠습니다.

일단 1번 노드가 시작 노드이므로 1번 노드를 탐색합니다. 그리고 1번 노드와 연결된 노드 중 탐색하지 않은 노드 하나를 선택해서 탐색합니다. 

이번에는 왼쪽에 있는 2번 노드를 탐색한다고 합시다. 
이젠 2번 노드의 이웃 노드 중 4번 노드를 탐색하고 
4번 노드의 이웃 노드인 9번 노드를 탐색합니다. 
그리고 9번 노드와 연결되어 있는 5번 노드를 탐색합니다. 

이제 5번 노드와 이웃인 2번 노드를 탐색하려고 합니다. 그런데 이미 2번 노드는 탐색을 완료,했으므로 탐색하지 않은 이웃 노드는 존재하지 않습니다. 그러므로 이전 노드로 돌아갑니다. 

이전 노드는 9번 노드입니다. 그런데 9번 노드에서도 탐색하지 않은 이웃 노드는 존재하지 않습니다. 그러므로 이전 노드인 4번으로 돌아갑니다. 

4번 노드에서도 탐색하지 않은 이웃 노드는 존재하지 않으므로 2번 노드로 돌아가고 2번 노드에서도 해당 이웃 노드는 존재하지 않으므로 1번 노드로 돌아갑니다.

이제 1번 노드에서 이웃하지 않은 노드를 찾아보면 3번 노드가 이에 해당됩니다. 따라서 3번 노드를 탐색합니다.
그리고 3번 노드의 탐색하지 않은 이웃 중 하나인 6번 노드를 탐색합니다.

이와 같은 방법으로 10번 11번 노드도 탐색해줍니다. 11번 노드까지 탐색을 완료하면 이웃 노드가 없으므로 3번 노드까지 다시 돌아갑니다.

3번 노드의 탐색하지 않은 이웃은 7, 8번 노드가 있는데 이 중 7번 노드 먼저 탐색합니다.

7번 노드는 탐색하지 않은 이웃 노드가 없으므로 다시 3번 노드로 돌아갑니다.

이제 3번 노드의 이웃 노드 중 탐색하지 않은 8번 노드를 탐색하면 모든 노드를 탐색하게 되므로 DFS를 종료합니다.

---

이제 깊이 우선 탐색을 어떻게 구현하는지에 대해 알아보겠습니다.

위에서 말한 알고리즘으로 재귀함수로도 구현할 수 있습니다.

그러나 재귀함수를 사용하지 않고 스택을 이용해서도 깊이 우선 탐색을 구현할 수 있습니다. 이 방법에 대해 상세히 알아보겠습니다.

그런데 깊이 우선 탐색은 왜 하필 스택을 이용할까요. 한 번 따져 봅시다. 
스택은 데이터가 처리되는 방식이 FILO(First In Last Out)입니다. 즉, 먼저 입력된 자료들이 늦게 처리되는 선입후출 방식입니다. 

스택에는 탐색해야 할 노드들을 저장해 줍니다. DFS 탐색 시 탐색할 노드는 스택의 top에 위치한 노드입니다. 탐색한 노드의 탐색하지 않은 이웃 노드들을 stack에 push합니다. 그리고 이 이웃 노드를 다시 탐색해줍니다. 즉, push한 노드중 top에 위치한 노드를 다시 꺼내서 탐색한다는 이야기가 됩니다.

따라서 깊이 우선 탐색(DFS)은 가장 최근에 탐색한 노드의 이웃노드를 먼저 탐색해야 하므로 선입후출 방식인 스택 자료구조가 적절하다고 볼 수 있습니다.

이제 위에서 알아보았던 그래프를 가지고 깊이 우선 탐색(DFS) 과정에서 스택안의 자료가 어떻게 변하는지 결과가 어떻게 해서 나오는지 알아보겠습니다.

일단 시작 노드는 1번 노드이므로 1번을 스택에 push 해주고 시작합니다.

탐색해줄 노드는 스택의 top이 됩니다. 즉, 1번이 top이므로 1번 노드를 탐색합니다. 

탐색한 1번 노드는 pop해줍니다. 그리고 1번 노드의 탐색하지 않은 이웃 노드를 스택에 push 합니다. 그래서 스택에 2와 3번 노드가 push됩니다.

그런데 이 때, 탐색하지 않은 이웃 노드를 구분하기 위해 bool형 check 배열을 도입합니다. 

check 배열은 탐색을 한 뒤 해당 노드 번호(x)에 해당하는 check[x]를 true로 set해 줍니다. 즉, 아직 탐색하지 않은 노드는 false이고, 탐색한 노드는 true가 됩니다.

그러므로 탐색하지 않은 이웃 노드는 이웃 노드 중 check[이웃노드번호]가 false인 경우 스택에 push해 줍니다.

그리고 다시 top에 있는 노드인 2번 노드를 탐색하면서 2번 노드를 pop해주고, 탐색하지 않은 이웃 노드(4, 5)를 push합니다.

이와 같은 방법으로 4번, 9번, 5번 노드를 탐색합니다. 근데 이 때, 5번 노드를 탐색한 뒤 앞에서 했던 대로 스택의 top에 있는 노드를 탐색해 주는데 top 노드가 방금 탐색 했던 5번 노드입니다. 왜 이런걸까요. 

사실 5번 노드는 2번 노드를 탐색할 때 이웃 노드로 스택에 push가 먼저 되었었습니다. 그런데 9번 노드의 이웃 노드로 먼저 탐색이 되버린거죠. 이런 경우에도 아까 정의한 check 배열을 이용하면 탐색했는지 안했는지 구분할 수 있으므로, 만약 탐색해야 할 노드의 check 배열이 true인 경우 이미  탐색했다는 뜻이므로 탐색하지 않고 스택에서 pop만 해주면 됩니다.

그리고 같은 방법으로 스택이 빌 때까지 탐색해주면 깊이 우선 탐색(DFS) 결과를 구할 수 있습니다. 

DFS의 시간복잡도는 인접리스트로 구현시 O(V+E), 인접행렬로 구현시 O(V^2) 입니다.

---

DFS 실행했을 때 방문한 정점을 순서대로 출력하는 코드를 작성해 보았습니다. STL stack 컨테이너를 이용하여 구현하였으며 입력은 정점의 수(N), 간선의 수(M), 탐색 시작하는 정점 번호(V)를 순서대로 입력받고 M개 줄 만큼 간선의 양 끝점(u v)을 입력받습니다. 

백준 문제 (DFS와 BFS;1260)(https://www.acmicpc.net/problem/1260) 문제와 같은 입출력을 가집니다. 문제에서는 DFS 뿐만 아니라 BFS결과도 같이 출력해야 하지만..ㅎ 한 번 풀어보시는 걸 추천합니다.

소스코드 : https://gist.github.com/fpdjsns/afdfb714cfbc167d455e75f206b7b91e

[실행 결과]