깊이 우선 탐색

수치해석 소프트웨어 마지막 수정: 2026-08-29 04:12:18

1. 개요[편집]

깊이 우선 탐색 Depth-first search, DFS
대상	유향·무향 그래프 $G=(V,E)$
복잡도	$\Theta(V+E)$ (인접 리스트 기준)
추가 공간	$O(V)$ — 색·시각 배열 + 스택
핵심 산출물	DFS 숲 · 발견시각 $d[v]$ · 종료시각 $f[v]$
간선 분류	트리 · 후방 · 전방 · 교차
대표 정리	괄호 정리 · 흰 경로 정리
파생	위상 정렬 · SCC · 이중연결 성분 · 사이클 검출

깊이 우선 탐색(depth-first search, DFS)은 그래프에서 갈 수 있는 곳까지 최대한 깊이 들어간 뒤 막히면 한 걸음씩 되돌아 나오며 미방문 정점을 훑는 순회 전략이다. 코드로는 열 줄이 안 되고, 재귀로 쓰면 사실상 “인접한 곳에 대해 자기 자신을 부른다”가 전부다.

이 싱거운 절차가 그래프 알고리즘의 절반을 떠받치는 이유는 순회 자체가 아니라 순회가 남기는 부산물 때문이다. DFS 는 정점마다 “언제 들어갔고 언제 나왔는가”라는 두 개의 시각을 찍고, 그 시각들이 그래프의 구조를 놀랄 만큼 정확하게 인코딩한다. 사이클이 있는지, 위상 순서가 무엇인지, 어느 정점 덩어리가 서로 왕복 가능한지, 어느 정점을 지우면 그래프가 두 조각 나는지 — 전부 같은 한 번의 DFS 에 번호 몇 개를 더 얹어서 선형 시간에 나온다. 타잔이 1972년 논문 한 편에서 강한 연결 요소와 이중연결 성분을 동시에 해치운 것도 이 때문이다.¹

훑는 순서만 놓고 너비 우선 탐색과 비교하면 “스택이냐 큐냐”의 차이일 뿐이지만, 쓸모의 결이 다르다. 가중치 없는 최단경로·레벨 구조·경로 계획은 BFS 몫이고, 구조 분해는 거의 전부 DFS 몫이다.

2. 발견 시각과 종료 시각[편집]

정점에 흰색(미방문)·회색(방문했고 아직 재귀 안)·검은색(종료)의 삼색을 주고, 색이 바뀌는 순간마다 전역 시계를 1 씩 올려 찍는다.

time = 0
dfs(u):
    color[u] = GRAY;  d[u] = ++time
    for each edge (u,v):
        if color[v] == WHITE: parent[v] = u; dfs(v)
    color[u] = BLACK; f[u] = ++time

모든 정점을 한 번씩 시도하면 방문 트리들이 모여 DFS 숲이 된다. 시계는 정점당 두 번 도니 $1 \le d[u] < f[u] \le 2|V|$ 이고, 총 비용은 정점 한 번 + 간선 한 번이라 $\Theta(V+E)$ 다.

여기서 두 개의 정리가 나온다. 둘 다 증명은 짧지만 이후 모든 응용이 여기에 기댄다.

괄호 정리. 임의의 두 정점 $u,v$ 에 대해 구간 $[d[u],f[u]]$ 와 $[d[v],f[v]]$ 는 완전히 분리되거나 한쪽이 다른 쪽에 완전히 포함된다. 부분적으로 겹치는 일은 없다. 재귀 호출이 스택이니 당연한 이야기인데, 덕분에 ” $v$ 가 $u$ 의 후손이다”가 " $d[u] < d[v] < f[v] < f[u]$ "라는 정수 두 개 비교로 환원된다. 트리 조상 판정을 $O(1)$ 에 하는 이 트릭은 옥트리나 BVH 같은 트리 자료구조 코드에도 그대로 재활용된다.

흰 경로 정리. $v$ 가 DFS 숲에서 $u$ 의 후손이 되는 것은, 시각 $d[u]$ 에 $u$ 에서 $v$ 로 가는 경로가 전부 흰 정점으로만 이루어져 있는 것과 동치다. “지금 안 잡으면 남이 잡는다”는 직관을 정확히 진술한 것으로, 도달 가능성 논증의 주력 무기다.

3. 간선 분류[편집]

DFS 를 돌리다 간선 $(u,v)$ 를 처음 마주쳤을 때 $v$ 의 색을 보면 간선이 네 종류로 갈린다.

종류	마주쳤을 때 $v$ 의 색	시각 관계	뜻
트리 간선	흰색	$d[u] < d[v] < f[v] < f[u]$	DFS 숲의 부모→자식
후방 간선	회색	$d[v] \le d[u] < f[u] \le f[v]$	조상으로 되돌아감
전방 간선	검은색, $d[u] < d[v]$	$d[u] < d[v] < f[v] < f[u]$	후손으로 건너뜀
교차 간선	검은색, $d[v] < d[u]$	$d[v] < f[v] < d[u] < f[u]$	이미 끝난 다른 가지로

한 줄로 외우려면 **“종료 시각이 아직 안 찍힌 정점으로 가는 간선이 후방 간선”**이고, 나머지는 $f[v] < f[u]$ 를 만족한다. 이 관찰에서 곧바로 두 가지가 따라온다.

유향그래프에 사이클이 있다 $\iff$ 후방 간선이 있다. 사이클 검출이 DFS 한 줄로 끝나는 이유이자, 위상 정렬이 종료 시각 내림차순인 이유다.
무향그래프에는 트리 간선과 후방 간선밖에 없다. 전방·교차 간선이 있으려면 그 간선을 반대 방향에서 이미 봤어야 하는데, 무향이라 그때 트리 또는 후방으로 이미 분류됐기 때문이다.

주의할 점은 분류가 그래프의 내재적 성질이 아니라는 것이다. 시작 정점을 바꾸거나 인접 리스트 순서를 바꾸면 어제 교차 간선이던 것이 오늘 전방 간선이 된다. 불변인 것은 “후방 간선이 하나라도 존재하는가”(= 사이클 유무)뿐이다. 여기서 강한 연결 요소 문서가 경고하는 그 버그가 나온다 — visited 불리언 하나만 들고 회색과 검은색을 구별하지 않으면 교차 간선을 후방 간선으로 오인해 멀쩡한 DAG 를 “순환 참조”라고 신고한다. 색은 두 가지가 아니라 세 가지다.

4. DFS 위에 얹히는 것들[편집]

DFS 가 유난히 재사용되는 것은, 위 골격에 배열 하나와 갱신 규칙 한 줄을 얹으면 완전히 다른 문제가 풀리기 때문이다.

사이클 검출·위상 정렬 — 회색 정점으로 가는 간선을 잡으면 사이클, 후위(종료) 순서를 뒤집으면 위상 순서.
강한 연결 요소 — 타잔은 low[v](스택에 살아 있는 정점 중 $v$ 의 부분트리에서 닿는 최소 발견번호)를 얹어 DFS 한 번에, 코사라주는 종료 시각 순서 + 역그래프 DFS 로 두 번에 구한다. 그 위에 2-SAT 이, 그 위에 희소행렬 블록 삼각화가 얹힌다.
이중연결 성분·단절점·다리 — 무향그래프 판. 여기서는 후방 간선만 있으므로 $\mathrm{low}[v] = \min\{\,d[v],\ d[w]\ (\text{후방 } v\to w),\ \mathrm{low}[c]\ (\text{자식 } c)\,\}$ 로 정의한다. 그러면
- 루트가 아닌 $u$ 가 단절점(articulation point) $\iff$ 어떤 자식 $c$ 에 대해 $\mathrm{low}[c] \ge d[u]$ ,
- 루트는 DFS 트리에서 자식이 2개 이상일 때만 단절점,
- 간선 $(u,c)$ 가 다리(bridge) $\iff \mathrm{low}[c] > d[u]$ .
부등호가 $\ge$ 냐 $>$ 냐 하나로 단절점과 다리가 갈린다는 게 이 코드의 악명 높은 함정이고, 두 번째 조건(루트 예외)을 빠뜨리는 것이 그다음이다. 간선을 스택에 쌓아 두었다가 조건이 걸릴 때 팝하면 이중연결 성분 자체를 뱉는다. 구조·회로 문제에서는 단절점이 곧 단일 고장점이라, 이 세 줄이 그대로 신뢰성 해석 도구가 된다.
백트래킹과 분기 탐색 — 해 공간 트리 위의 DFS 다. 분지한정법, SAT 풀이기의 DPLL, 제약 프로그래밍 솔버가 전부 “깊이 들어가고 막히면 되돌아온다”는 이 골격 위에 가지치기를 얹은 것. 그래프가 미리 존재하지 않고 탐색하면서 생성된다는 점만 다르다. 메모리가 경로 길이에만 비례한다는 DFS 의 성질이 여기서 결정적이다 — BFS 로 해 공간을 훑으면 프런티어가 지수로 부풀어 메모리부터 터진다.

5. 재귀가 터진다[편집]

교과서 코드는 재귀지만, 실무에서 DFS 를 처음 프로덕션에 올리면 십중팔구 스택 오버플로로 인사한다. 이유가 구조적이다. DFS 의 재귀 깊이는 최악의 경우 $|V|$ 이고, “최악”이 병적인 그래프가 아니라 긴 사슬 하나면 충분하다. 호출 그래프, 회로 넷리스트, 격자에서 만든 인접 그래프는 전부 지름이 크다.

리눅스의 기본 스레드 스택은 8 MB, 윈도의 기본 스레드는 1 MB 다. 프레임 하나가 지역변수와 이터레이터까지 해서 수십~백 바이트쯤 나가므로 감당 가능한 깊이는 대략 $10^5$ 자릿수다. 정점 100만 개짜리 격자 플러드 필이 재귀로 짜인 순간 그 프로그램은 이미 죽어 있다.²

해법은 명시적 스택으로 펼치는 것인데, 여기에도 결이 있다.

어설픈 변환 — “스택에 이웃을 전부 밀어 넣는다” 판은 순회 순서가 재귀와 달라지고, 무엇보다 종료 시각과 low 를 못 찍는다. 단순 도달성 판정에는 쓸 수 있지만 타잔이나 단절점 코드에 그대로 넣으면 조용히 틀린다.
제대로 된 변환 — 정점마다 “인접 리스트를 어디까지 봤는가”를 나타내는 간선 인덱스를 함께 스택에 올려, 재귀 호출 지점을 상태 기계로 흉내 낸다. 그러면 회색·검은색 전이 시점이 재귀와 정확히 일치해 $d$ , $f$ , low 를 모두 살릴 수 있다. 스택 원소가 (정점, 간선 인덱스) 쌍인 코드를 보면 그 저자는 이 함정을 이미 밟아 본 사람이다.
꼼수 — 스레드를 큰 스택으로 새로 띄우거나(ulimit -s, pthread_attr_setstacksize) 세그먼트 스택을 쓰는 언어에 맡기는 방법. 급할 때는 통하지만 깊이 상한이 여전히 하드웨어 상수에 걸려 있으므로 근본 해결은 아니다.

덤으로 알아둘 것 하나. DFS 는 병렬화가 지독히 어렵다. 인접 리스트 순서까지 그대로 재현하는 사전식 DFS 를 구하는 문제는 P-완전이라, 다항 로그 시간 병렬 알고리즘이 있으리라 기대하기 어렵다.³ BFS 가 레벨 단위로 시원하게 병렬화되는 것과 정확히 대비되며, 대규모 그래프 처리 프레임워크가 하나같이 BFS 계열 프리미티브만 제공하는 실무적 이유이기도 하다.

6. 시뮬레이션 쪽에서 만나는 자리[편집]

연결 성분과 라벨링 — 메시의 조각이 몇 덩어리인지, 메시 생성 결과에 떠 있는 고아 요소가 있는지, 이진화 이미지의 블롭이 몇 개인지. 격자에서는 union-find 나 호센-코프만이 더 흔하지만(퍼콜레이션 문서 참고), 비정렬 메시에서는 DFS 가 가장 간단하다.
법선 방향 전파 — 삼각형 메시의 앞뒷면을 일관되게 맞추는 작업은 DFS 로 이웃 면을 훑으며 공유 모서리의 방향이 반대인지 검사하는 것이다. 도중에 모순이 잡히면 그 메시는 뫼비우스 띠 같은 비가향(non-orientable) 곡면이거나 애초에 위상이 망가진 것이다.
접촉 아일랜드 — 물리 엔진은 매 스텝 충돌 감지 결과로 접촉 그래프를 만들고, 연결 성분(아일랜드)마다 따로 솔버를 돌린다. 아일랜드 분해가 곧 병렬화 단위이자 “잠든” 물체를 통째로 건너뛰는 최적화의 단위다.
미로 생성 — 무작위 순서로 이웃을 고르는 DFS 는 그 자체로 완벽 미로(사이클 없는 통로) 생성기다. 길게 구불구불한 통로가 나오는 특유의 편향이 있고, 이게 싫으면 최소 신장 트리 계열(프림·크러스컬)이나 윌슨 알고리즘을 쓴다.
컴파일러와 해석기 — 지배자 트리 계산, 자연 루프 검출(후방 간선이 곧 루프 후미변), 상호 재귀 함수 묶기, 데이터 흐름 분석의 역후위 순서 반복. 시뮬레이션 코드를 컴파일하는 쪽에서도 결국 같은 도구가 돈다.

7. 관련 문서[편집]

Tarjan, R. E. (1972). “Depth-first search and linear graph algorithms”. SIAM J. Comput. 1(2), 146–160. 제목이 겸손해 보이지만 내용은 “DFS 에 번호를 붙이면 이만큼 나온다”는 시위에 가깝다. 이후 40년간 그래프 알고리즘 논문의 국룰이 “일단 low 를 정의하고 시작”이 된 데는 이 논문 지분이 크다. ↩
옛날 그래픽 툴에서 페인트통으로 큰 영역을 칠하면 프로그램이 통째로 죽던 그 현상의 정체가 대체로 이것이다. 요즘 구현이 스캔라인 방식(가로 구간 단위로 스택에 넣기)을 쓰는 것은 예뻐서가 아니라 스택 깊이를 픽셀 수가 아니라 구간 수로 낮추려는 생존 본능이다. ↩
Reif, J. H. (1985). “Depth-first search is inherently sequential”. Inf. Process. Lett. 20(5), 229–234. 정확히는 사전식 DFS 순서를 구하는 판정 문제가 P-완전이라는 결과다. 인접 리스트 순서를 지키라는 요구를 풀어 주면 사정이 나아져서, 이후 무작위 병렬 알고리즘(RNC)이 나왔다. 그래도 “그냥 재귀로 짜면 되는 걸 왜 그렇게까지” 소리를 듣는 분야인 것은 변함이 없다. ↩