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

기본 개념

---

'깊이 우선 탐색'은 '너비 우선 탐색'과 마찬가지로 그래프(혹은 트리와 같은 자료구조)를 탐색하는 방법 중 하나다. 루트 노드에서부터 접근할 수 있는 최대한 깊은 노드까지 탐색을 한 뒤, 전으로 돌아와 다른 노드의 끝까지 다시 탐색하는 방식을 반복해 탐색을 수행하는 알고리즘이다.

 

갈 수 있는 최대 깊이까지 탐색을 수행한 뒤, 다음 탐색으로 넘어간다는 알고리즘 수행 방식으로 인해 너비 우선 탐색에 보다 탐색 속도가 느리다. 하지만 특정 목표 노드가 있을 경우 해당 노드까지의 경로 혹은 도달 가능 여부를 빠르게 파악할 수 있다는 장점이 존재한다.

 

 

 

예시

---

위와 같은 총 7개의 노드를 가진 그래프를 예시로 생각해보자. 루트 노드는 A로 설정해보자. 이제 좌에서 우 순서로 깊이 우선 탐색을 진행하겠다. A와 연결되어 있는 노드는 B와 C다. 이제 좌측에 있는 B노드로 접근하겠다.

 

이제 B 노드의 근접 노드를 생각해보자. A는 이미 접근한 노드이기 때문에 제외한다. D와 E 사이에서 하나를 선택해야 한다. 죄에서 우 순서로 진행하기로 했으니 D에 접근하도록 하겠다.

 

D 노드에 들어왔다. 이때 만일 목표 노드가 D였다면 'A-B-D'로 A노드에서 D노드까지 접근하는 경로를 구할 수 있다. D노드가 목표 노드가 아니었다면 계속해서 탐색을 진행할 수 있다. 그런데 그림을 한번 보자. D노드의 근접 노드는 B뿐이다. 하지만 B노드에서 D노드로 왔으니, 즉 B노드는 이미 접근했던 노드이니 더 이상 탐색할 노드가 없다. 그렇다면 이제 B노드로 돌아온다. 이제 B 노드에서 접근하지 않은 노드로 탐색을 이어간다.

 

만일 E노드가 목표 노드였다면 'A-B-E' 경로를 얻을 수 있다. 당연하게도 계속 탐색을 이어갈 수 있다. 하지만 아까와 같이 E노드에서 탐색할 곳은 더 이상 없기 때문에 B노드로 올라간다. B노드를 살펴보니 B노드 또한 더 이상 탐색할 곳이 없다. A 노드로 돌아가자. A노드에서 탐색할 수 있는 곳은 C노드다. 이제 C노드로 탐색을 이어간다.

 

여기까지 왔으면 어떤 방식으로 알고리즘이 진행되는지 이해가 됐을 것이라 생각한다. 같은 방식으로 탐색을 진행하면 된다. 같은 내용이 반복되기 때문에 과정을 빠르게 살펴보도록 하겠다.

 

 

위의 설명이 어떤 방식으로 진행되었는지 이해했다면 깊이 우선 탐색의 메커니즘을 이해할 수 있을 것이다. 따로 목표 노드를 두고, break 하지 않으면 루트 노드가 마지막 노드까지 탐색하는 모든 경로를 파악할 수 있다. 위의 예시는 목표 노드 없이 끝까지 탐구를 진행한 경우이며, 목표 노드가 있다면 목표 노드 탐색 시 바로 빠져나와 불필요한 연산을 줄이도록 하자.

 

 

 

예시 문제

---

https://www.acmicpc.net/problem/17265

17265번: 나의 인생에는 수학과 함께