깊이우선탐색
-
[알고리즘] 깊이 우선 탐색 (DFS, Depth-First Search)Algorithm 2020. 12. 10. 18:48
깊이 우선 탐색 (DFS, Depth-First Search)는 그래프 탐색 방법 중 한 정점에서 시작하여 모든 정점을 탐색하기 위한 방법이다. 깊이 우선 탐색은 간단하게 "한쪽 방향으로 파고들어 탐색하는 방식"으로 미로에서 길을 찾는 것과 같다. 시작점으로부터 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색한다. 장점 현 경로상의 노드만 저장하면 되기 때문에 그래프 높이 만큼의 저장공간을 필요로 한다. 즉, 최대저장공간의 수요가 비교적 적다. 목표가 위한 깊이가 깊을 경우 해를 빠르게 구할 수 있다. 단점 해가 없는 경로에 깊이 빠질 수 있다. 목표에 이르는 경로가 다수인 경우, 목표에 닿으면 팀색을 끝내기 때문에 최적의 해가 아닐 수 있다. 주로 모든 경로를 탐색해야하거나, 경로 탐색에 조건이 ..