깊이 우선 탐색(Depth-First Search, DFS)은 한 경로를 끝까지 따라간 뒤, 막히면 되돌아와서 다른 경로를 탐색하는 그래프 탐색 알고리즘입니다. Stack(LIFO)을 사용하거나 재귀 호출로 구현하며, Breadth-First Search가 너비 방향으로 한 겹씩 탐색하는 것과 달리 깊이 방향으로 먼저 파고듭니다. 이 글에서는 DFS의 핵심 아이디어와 알고리즘, 시간·공간 복잡도, DFS의 한계, 그리고 위상 정렬·사이클 탐지 등의 활용 사례를 살펴봅니다.
핵심 아이디어
DFS는 미로를 탐험하는 것에 비유할 수 있다. 갈림길에서 한 방향을 선택하여 끝까지 가보고, 막다른 길에 도달하면 가장 최근의 갈림길로 되돌아와서(backtrack) 아직 가보지 않은 다른 길을 시도한다. 이 "되돌아오기" 동작이 DFS의 본질이며, 이는 Stack의 LIFO 특성 또는 재귀 호출의 호출 스택과 자연스럽게 대응된다.
위 그래프에서 노드 A부터 DFS를 수행하면, A에서 B로, B에서 D로 깊이 방향으로 먼저 내려간다. D에서 더 갈 곳이 없으면 B로 돌아와 E를 탐색하고, 다시 A로 돌아와 C, F 순서로 탐색한다. 탐색 순서는 A → B → D → E → C → F가 된다.
알고리즘
재귀 구현
DFS의 가장 자연스러운 구현은 재귀다. 호출 스택이 곧 탐색 스택 역할을 한다.
function DFS(graph, node, visited)
visited.add(node)
for each neighbor of node do
if neighbor not in visited then
DFS(graph, neighbor, visited)
반복 구현 (명시적 스택)
재귀 깊이가 깊어지면 스택 오버플로가 발생할 수 있다. 이때는 명시적 Stack을 사용하여 반복적으로 구현한다.
function DFS-Iterative(graph, start) returns visited order
stack ← empty stack
visited ← empty set
stack.push(start)
while stack is not empty do
current ← stack.pop()
if current not in visited then
visited.add(current)
for each neighbor of current do
if neighbor not in visited then
stack.push(neighbor)
반복 구현에서는 꺼낼 때 방문 처리한다는 점에 주의하자. BFS에서는 큐에 넣을 때 방문 처리하지만, DFS의 반복 구현에서는 같은 노드가 스택에 여러 번 들어갈 수 있으므로 꺼낼 때 처리해야 한다1.
탐색 예시
아래 그래프에서 A를 시작으로 DFS를 수행하는 과정을 단계별로 살펴보자.
A
/ \
B C
/ \ \
D E F
Step 1 — A를 방문한다. 이웃 B, C 중 B를 먼저 탐색한다.
Step 2 — B를 방문한다. 이웃 D, E 중 D를 먼저 탐색한다.
Step 3 — D를 방문한다. 미방문 이웃이 없으므로 B로 되돌아간다.
Step 4 — B에서 아직 방문하지 않은 E를 탐색한다.
Step 5 — E를 방문한다. 미방문 이웃이 없으므로 B → A로 되돌아간다.
Step 6 — A에서 아직 방문하지 않은 C를 탐색한다.
Step 7 — C를 방문하고, 이웃 F를 탐색한다.
Step 8 — F를 방문한다. 미방문 이웃이 없다. 탐색 종료.
최종 방문 순서: A → B → D → E → C → F. BFS의 A → B → C → D → E → F와 비교하면, DFS는 B 방향을 끝까지 탐색한 뒤에야 C 방향으로 넘어가는 것을 볼 수 있다.
Python 구현
from typing import Optional
def dfs_recursive(
graph: dict[str, list[str]],
start: str,
visited: Optional[set[str]] = None,
order: Optional[list[str]] = None,
) -> list[str]:
"""재귀 DFS. 방문 순서를 반환한다."""
if visited is None:
visited = set()
if order is None:
order = []
visited.add(start)
order.append(start)
for neighbor in graph.get(start, []):
if neighbor not in visited:
dfs_recursive(graph, neighbor, visited, order)
return order
def dfs_iterative(
graph: dict[str, list[str]],
start: str,
) -> list[str]:
"""반복 DFS. 명시적 스택을 사용한다."""
visited: set[str] = set()
stack = [start]
order: list[str] = []
while stack:
current = stack.pop()
if current in visited:
continue
visited.add(current)
order.append(current)
# 스택은 LIFO이므로, 역순으로 넣어야 원래 순서대로 탐색
for neighbor in reversed(graph.get(current, [])):
if neighbor not in visited:
stack.append(neighbor)
return order반복 구현에서 이웃을 reversed 순서로 스택에 넣는 이유는, 스택이 LIFO이므로 마지막에 넣은 것이 먼저 나오기 때문이다. 인접 리스트의 첫 번째 이웃을 먼저 탐색하려면 역순으로 넣어야 한다.
시간 복잡도와 공간 복잡도
DFS의 시간 복잡도는 BFS와 동일하게 이다. 모든 노드를 한 번씩, 모든 간선을 한 번씩 처리하기 때문이다.
공간 복잡도는 이다. 최악의 경우 그래프가 일직선(체인)이면 스택에 개의 노드가 모두 들어갈 수 있다. 그러나 일반적으로는 BFS보다 메모리 효율이 좋다. BFS는 한 레벨의 모든 노드를 큐에 유지해야 하므로 까지 커질 수 있지만, DFS는 현재 경로의 노드만 스택에 유지하면 되므로 2에 그친다.
DFS의 한계
DFS는 최단 경로를 보장하지 않는다. 깊이 방향으로 먼저 탐색하므로, 목표에 도달하더라도 그것이 가장 짧은 경로라는 보장이 없다. 최단 경로가 필요하면 Breadth-First Search를 사용해야 한다.
또한 무한한 깊이의 그래프나 순환이 있는 그래프에서는 DFS가 한 경로를 무한히 따라갈 수 있다. 이를 방지하려면 방문 검사(visited)를 반드시 수행하거나, 깊이 제한(depth limit)을 설정해야 한다. 깊이 제한 DFS를 반복적으로 수행하는 것이 반복 심화 탐색(Iterative Deepening DFS, IDDFS)이며, 이는 BFS의 최적성과 DFS의 메모리 효율을 결합한 전략이다.
어디에 쓰이는가
DFS는 그래프의 구조적 성질을 파악하는 데 특히 강력하다. 위상 정렬(topological sort)은 DAG에서 DFS의 종료 순서를 역순으로 나열한 것이고, Tarjan 알고리즘은 DFS를 사용하여 강연결 요소(strongly connected components)를 찾는다. 사이클 탐지, 이분 그래프 판별, 미로 생성 알고리즘에서도 DFS가 핵심이다. 컴파일러의 구문 분석(parsing)이나 퍼즐의 모든 해를 찾는 백트래킹(backtracking) 역시 DFS의 응용이다.
출처
- Cormen, T. H. et al. (2022) Introduction to Algorithms. 4th edn. Cambridge, MA: MIT Press. Chapter 20.3.
- Russell, S. and Norvig, P. (2021) Artificial Intelligence: A Modern Approach. 4th Global edn. Harlow: Pearson. Chapter 3.4.3.