깊이 우선 탐색이란?
깊이 우선 탐색(DFS, Depth-First Search)은 한 방향으로 갈 수 있는 데까지 깊이 들어갔다가, 더 갈 곳이 없으면 되돌아와(백트래킹) 다른 길을 탐색하는 그래프·트리 순회 방법입니다. 너비 우선 탐색(BFS)과 짝을 이루는 기본 탐색 기법입니다.
핵심 한 줄: "일단 한 길로 끝까지 가 본다." 막다른 길에 닿으면 가장 최근 갈림길로 돌아와 안 가본 길을 시도합니다.
스택으로 동작한다
DFS의 "되돌아오기"는 스택으로 자연스럽게 표현됩니다. 가장 흔한 구현은 재귀인데, 이때는 함수 호출 스택이 그 역할을 대신합니다. 명시적 스택을 써서 반복문으로 구현할 수도 있습니다.
어느 쪽이든 방문 표시(visited)가 필수입니다. 표시가 없으면 사이클이 있는 그래프에서 같은 노드를 무한히 맴돕니다.
동작 원리
1단계. 시작 노드를 방문 표시합니다.
2단계. 인접 노드 중 아직 안 가본 것 하나를 골라 그쪽으로 깊이 들어갑니다(재귀 호출).
3단계. 더 갈 곳이 없으면 호출이 끝나며 이전 노드로 되돌아옵니다. 거기서 또 다른 미방문 인접 노드를 시도합니다.
4단계. 모든 도달 가능한 노드를 방문할 때까지 반복합니다.
알고노트 시각화는 깊이 들어가는 간선과 막혀서 되돌아오는 순간을 색으로 구분해 단계별로 보여줍니다.
BFS와의 차이
| DFS | BFS | |
|---|---|---|
| 자료구조 | 스택(재귀) | 큐 |
| 탐색 순서 | 깊이 먼저 | 너비(가까운 것) 먼저 |
| 잘 맞는 문제 | 경로 존재·사이클 검출·위상 정렬·연결 요소 | 무가중치 최단 경로·최소 단계 |
가까운 것부터 봐야 하는 최단 거리 문제는 BFS, "끝까지 가 보며" 구조를 파악하는 문제는 DFS가 어울립니다.
시간복잡도와 공간복잡도
| 복잡도 | |
|---|---|
| 시간 | O(V + E) |
| 공간 | O(V) |
V는 정점 수, E는 간선 수입니다. 모든 정점과 간선을 한 번씩 보므로 O(V + E)입니다.
예시로 따라가기
0 - 1, 0 - 2, 1 - 3 간선이 있는 그래프에서 0부터 DFS:
- •0 방문 → 1로 깊이 → 3으로 깊이 → 3 막힘, 1로 복귀 → 1 막힘, 0으로 복귀 → 2로 깊이
- •방문 순서 예: 0 → 1 → 3 → 2
자주 하는 실수
- •방문 표시 누락: 사이클에서 무한 루프에 빠집니다. DFS의 1순위 함정입니다.
- •표시 타이밍: 노드에 들어갈 때 표시해야 같은 노드를 두 번 큐/스택에 넣지 않습니다.
- •재귀 깊이 한도: 매우 깊은 그래프는 호출 스택이 넘칠 수 있어 명시적 스택으로 바꾸기도 합니다.
알고노트에서 직접 확인하세요
DFS가 한 길로 깊이 들어가고, 막히면 되돌아와 다른 길을 시도하는 과정을 알고노트에서 단계별로 확인할 수 있습니다.