한 갈래를 끝까지 파고든 뒤 되돌아 나오는 그래프 탐색(Depth-First Search). 미로에서 한 길을 끝까지 가 보고 막히면 갈림길로 되돌아오는 방식이다.
동작
1
/ \
2 3
/ \
4 5
방문 순서: 1 → 2 → 4 → (막힘, 되돌아감) → 5 → (되돌아감) → 3
되돌아 나오는 것을 백트래킹이라 한다.
두 가지 구현
① 재귀 — 호출 스택이 곧 탐색 스택이다
void dfs(int node) {
visited[node] = true;
for (int next : graph[node])
if (!visited[next]) dfs(next);
}
② 명시적 스택 — 재귀 깊이가 위험할 때
Deque<Integer> stack = new ArrayDeque<>();
stack.push(start);
while (!stack.isEmpty()) {
int node = stack.pop();
if (visited[node]) continue;
visited[node] = true;
for (int next : graph[node]) stack.push(next);
}
왜 스택인가 — "가장 최근에 발견한 곳부터" 가야 깊이 파고든다. 그것이 LIFO다.
복잡도
- 시간 O(V + E) — — 정점 V개를 한 번씩, 간선 E개를 한 번씩
- 공간 O(V) — — 재귀 깊이(최악: 일자 그래프면 V)
BFS 대신 DFS를 쓰는 경우
| 상황 | 이유 |
|---|---|
| 경로의 존재만 확인 | 최단이 아니어도 되면 DFS가 메모리 유리 |
| 모든 경우의 수 탐색 | 백트래킹의 기본 골격(N-Queens, 순열) |
| 위상 정렬 | DFS 종료 순서의 역순이 곧 위상 순서 |
| 사이클 검출 | 현재 경로에 이미 있는 정점을 다시 만나면 사이클 |
| 연결 요소 세기 | 방문 안 한 정점마다 DFS 한 번 = 요소 개수 |
실무에서 어디에 있나
- 의존성 해석 — 빌드 도구가 모듈 의존 그래프를 위상 정렬로 푼다. 순환 참조 검출이 곧 DFS 사이클 검출이다(스프링의 순환 참조 오류)
- 디렉터리 순회 — 파일 트리를 파고드는 것이 DFS
- JSON·트리 직렬화 — 깊이 우선으로 내려간다
- 가비지 컬렉션의 마크 단계 — 루트에서 도달 가능한 객체를 그래프 탐색으로 표시
재귀 깊이 함정
정점이 10만 개인 일자 그래프에 재귀 DFS를 쓰면 StackOverflowError 가 난다.
자바 기본 스택은 스레드당 약 512KB~1MB다.
→ 명시적 스택으로 바꾸거나, new Thread(null, task, "dfs", 64 * 1024 * 1024) 로
스택 크기를 키운다. 알고리즘 문제에서 자주 걸리는 지점이다.