깊이 우선 탐색
덤프버전 : (♥ 0)
분류
1. 개요[편집]
Depth First Search, DFS
그래프 순회 방식의 일종. 거의 항상 너비우선탐색(BFS; Breadth First Search)과 비교되어 나온다.
2. 상세[편집]
트리나 그래프에서 한 루트로 탐색하다가 특정 상황에서 최대한 깊숙이 들어가서 확인한 뒤 다시 돌아가 다른 루트로 탐색하는 방식이다. 대표적으로 백트래킹에 사용한다. 일반적으로 재귀호출을 사용하여 구현하지만, 단순한 스택 배열로 구현하기도 한다. 구조상 스택 오버플로우를 유의해야 한다.[1]
갈림길이 나타날 때마다 '다른 길이 있다'는 정보만 기록하면서 자신이 지나간 길을 지워나간다. 그러다 막다른 곳에 도달하면 직전 갈림길까지 돌아가면서 '이 길은 아님'이라는 표식을 남긴다. 그렇게 갈림길을 순차적으로 탐색해 나가다 목적지를 발견하면 그대로 해답을 내고 종료.
단순 검색 속도 자체는 BFS에 비해서 느리다. 하지만 검색이 아닌 순회(traversal)를 할 경우는 많이 쓰인다. DFS는 특히 리프 노드에만 데이터를 저장하는 정렬 트리 구조에서 항상 순서대로 데이터를 방문한다는 장점이 있다. 백트래킹에 사용되는 이유도 공통 상위를 가지는 아래 리프 노드들을 한방에 잘라내버리는게 가능하기 때문이다.
자동 미로 생성에 많이 사용되는 알고리즘이기도 하다. 방향은 무작위로 해서 계속 뚫다가 막혀서 못 뚫으면 뚫을 수 있는 곳이 발견될 때까지 되돌아가서 다시 뚫고, 또 막히면 되돌아가고 이런 식으로 무한히 반복하다 보면 생긴다. 게다가 이 방식으로 미로를 만들면 빠져나가는 경로 또한 단 하나만 생긴다. 직접 보고 싶다면 이 동영상을 보자.
유향그래프에서 사이클이 있는지 판단하는 것도 가능하다. 즉, 어떤 한 노드에서 간선을 따라 방문하다 보면 자기 자신으로 돌아올 수 있는 경로가 있는지 확인할 수 있다.
3. 장단점[편집]
3.1. 장점[편집]
- 단지 현 경로상의 노드들만을 기억하면 되므로 저장 공간의 수요가 비교적 적다.
- 목표 노드가 깊은 단계에 있을 경우 해를 빨리 구할 수 있다.
3.2. 단점[편집]
- 해가 없는 경로에 깊이 빠질 가능성이 있다. 따라서 실제로는 미리 지정한 임의 깊이까지만 탐색하고 목표 노드를 발견하지 못하면 다음 경로를 따라 탐색하는 방법이 유용할 수 있다.
- 얻어진 해가 최단 경로가 된다는 보장이 없다. 이는 목표에 이르는 경로가 다수인 문제에 대해 깊이우선탐색은 해에 다다르면 탐색을 끝내버리므로, 이때 얻어진 해는 최적이 아닐 수 있다는 의미이다.
4. 소스 코드[편집]
4.1. C++[편집]
const int MAX = 100'001;
bool visited[MAX]; // 방문 배열. visited[node] = true이면 node는 방문이 끝난 상태이다.
void dfs(const vector<int> graph[], int current) { // graph는 인접 리스트, current는 현재 노드
visited[current] = true; // current 방문
for(int next: graph[current]) { // current의 인접 노드를 확인한다. 이 노드를 next라고 하자.
if(!visited[next]) { // 만일 next에 방문하지 않았다면
dfs(graph, next); // next 방문
}
}
}
4.2. Python[편집]
def dfs(graph:Dict, start:int): # Dict 자료형 형태로 준다. key는 노드, value는 인접노드를 가리킨다.
visited = {i:False for i in graph.keys()} # 방문 배열. visited[node] = True이면 node는 방문이 끝난 상태이다.
def search(current:int): # 재귀함수 정의
visited[current] = True # current 방문
for nxt in graph[current]: # current의 인접 노드를 확인한다. 이 노드를 nxt라고 하자.
if not visited[nxt]: # 만일 nxt에 방문하지 않았다면
search(nxt) #nxt 방문
search(start)
5. 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가 아닌 경우를 말한다.
DFS 트리를 사용하면 unrooted tree를 rooted tree로 만들 수 있다. 이 경우에는 Tree edge 이외의 간선이 존재하지 않게 된다.
이 문서의 내용 중 전체 또는 일부는 2023-11-17 06:40:41에 나무위키 깊이 우선 탐색 문서에서 가져왔습니다.