그래프나 트리를, 한 길을 갈 수 있는 데까지 나아가고 막다른 곳에 이르면 되돌아와 다른 길로 나아가는 순서로 방문하는 탐색 방법. 재귀나 스택으로 구현하며, 미로 탐색, 연결 요소나 사이클의 검출, 위상 정렬 등에 쓰인다. 영어 머리글자로 DFS라고도 한다.
일본어 명칭: 深さ優先探索
깊이 우선 탐색(Depth-First Search)은(는) 자료 구조와 알고리즘 등 1개 분야의 연습 문제 3개에 나와요.
분야: 자료 구조와 알고리즘
정답: C. A, B, D, E, F, C
A에서 B로 나아가고, B의 이웃 중 처음으로 방문하지 않은 D로 나아갑니다. D의 이웃은 방문한 B뿐이므로 B로 돌아가 다음 E로 나아가고, E에서 방문하지 않은 F로, F에서 그 이웃인 C로 나아갑니다. 따라서 A, B, D, E, F, C의 순서입니다. A, B, C, D, E, F는 출발점에서 가까운 순서로 방문하는 너비 우선 탐색의 순서입니다. A, B, D, E, C, F는 E에서 방문하지 않은 F로 나아가지 않고 돌아가 버렸으므로 깊이 우선 탐색의 순서가 되지 않습니다.
A, B, D, E, C, F는 E에서 방문하지 않은 F로 나아가지 않고 돌아가 버렸으므로 깊이 우선 탐색의 순서가 되지 않습니다.
간선에 방향이 없는 그래프에서 각 정점의 이웃 정점이 다음과 같다. A: B, C / B: A, D, E …깊이 우선 탐색(재귀나 스택을 사용)은 한 길을 갈 수 있는 데까지 나아가므로, 돌아가는 경로로 먼저 도달하는 경우가 있어 최단이 보장되지 않습니다.
간선에 가중치가 없는 그래프에서, 출발점에서 각 정점까지의 최소 간선 수를 구하고 싶다. 적합한 탐색 방법…위상 정렬은 방향이 있고 사이클이 없는 그래프(DAG)에서 모든 간선이 앞에서 뒤로 향하도록 정점을 나열하는 조작으로, 들어오는 간선이 없는 정점부터 차례로 꺼내는 방법(칸 알고리즘)이나 깊이 우선 탐색으로 구할 수 있습니다.
작업 A~E에 'A는 C보다 앞', 'B는 C보다 앞', 'C는 D보다 앞', 'B는 E보다 앞', 'E는…재귀(Recursion) 너비 우선 탐색(Breadth-First Search) 스택(Stack) 다익스트라 알고리즘(Dijkstra's Algorithm) 동적 계획법(Dynamic Programming) 시간 복잡도(Time Complexity) 안정 정렬(Stable Sort) 연결 리스트(Linked List) 이진 탐색 트리(Binary Search Tree) 이진 탐색(Binary Search)