깊이 우선 탐색
1. 개요
Depth First Search. 흔히 줄여서 DFS로 쓴다. 한국어 표기는 깊이 우선 탐색.
거의 항상 넓이우선탐색(BFS; Breadth First Search)과 비교되어 나온다.
2. 상세
트리나 그래프에서 한 루트로 탐색하다가 특정 상황에서 최대한 깊숙히 들어가서 확인한 뒤 다시 돌아가 다른 루트로 탐색하는 방식이다. 대표적으로 백트래킹에 사용한다. 일반적으로 재귀호출을 사용하여 구현하지만, 단순한 스택 배열로 구현하기도 한다. 구조상 스택 오버플로우를 유의해야 한다.[1]
갈림길이 나타날 때마다 '다른 길이 있다'는 정보만 기록하면서 자신이 지나간 길을 지워나간다. 그러다 막다른 곳에 도달하면 직전 갈림길까지 돌아가면서 '이 길은 아님'이라는 표식을 남긴다. 그렇게 갈림길을 순차적으로 탐색해 나가다 목적지를 발견하면 그대로 해답을 내고 종료.
단순 검색 속도 자체는 BFS에 비해서 느리다. 하지만 검색이 아닌 트래버스(traverse)를 할 경우는 많이 쓰인다. DFS는 특히 리프 노드에만 데이터를 저장하는 정렬 트리 구조에서 항상 순서대로 데이터를 방문한다는 장점이 있다. 백트래킹에 사용되는 이유도 공통 상위를 가지는 아래 리프 노드들을 한방에 잘라 내 버리는게 가능하기 때문이다.
자동 미로 생성에 많이 사용되는 알고리즘이기도 하다. 방향은 무작위로 해서 계속 뚫다가 막혀서 못 뚫으면 뚫을 수 있는 곳이 발견될 때까지 되돌아가서 다시 뚫고, 또 막히면 되돌아가고 이런 식으로 무한히 반복하다 보면 생긴다. 게다가 이 방식으로 미로를 만들면 빠져나가는 경로 또한 단 하나만 생긴다. 직접 보고 싶다면 이 동영상을 보자.
DFS를 잘만 이용하면 방향 있는 그래프에서 사이클(cycle)이 있는지 판단하는 것도 가능하다. 즉 어떤 한 임의의 노드에서 길을 따라 가보면 자기 자신으로 돌아올 수 있는 경로가 있는지 확인할 수 있다.
3. 장단점
3.1. 장점
- 단지 현 경로상의 노드들만을 기억하면 되므로 저장 공간의 수요가 비교적 적다.
- 목표 노드가 깊은 단계에 있을 경우 해를 빨리 구할 수 있다.
3.2. 단점
- 해가 없는 경로에 깊이 빠질 가능성이 있다. 따라서 실제로는 미리 지정한 임의 깊이까지만 탐색하고 목표 노드를 발견하지 못하면 다음 경로를 따라 탐색하는 방법이 유용할 수 있다.
- 얻어진 해가 최단 경로가 된다는 보장이 없다. 이는 목표에 이르는 경로가 다수인 문제에 대해 깊이우선탐색은 해에 다다르면 탐색을 끝내버리므로, 이때 얻어진 해는 최적이 아닐 수 있다는 의미이다.
4. DFS 트리
한 정점을 두번 이상 방문하지 않는 연결그래프에서 DFS트리라는 유향트리 구조가 만들어진다.
- Tree edge란 DFS중 a정점을 방문한 후 b정점을 처음 방문할 때, a→b의 유향간선을 말한다.
- Back edge란 DFS중 a정점을 방문한 후 이미 방문한 b 정점을 방문할 때, b가 a의 조상일 때 a→b의 유향간선을 말한다,
- Forward edge란 DFS중 a정점을 방문한 후 이미 방문한 b 정점을 방문할 때, a가 b의 조상일 때 a→b의 유향간선을 말한다.
- Cross edge란 DFS중 a정점을 방문한 후 이미 방문한 b 정점을 방문할 때, a→b의 유향간선이 Back edge나 Forward edge가 아닌 경우를 말한다.