> [!abstract] Introduction > 깊이 우선 탐색(*Depth-First Search*, DFS)은 한 경로를 끝까지 따라간 뒤, 막히면 되돌아와서 다른 경로를 탐색하는 그래프 탐색 알고리즘입니다. [[Stack]](LIFO)을 사용하거나 재귀 호출로 구현하며, [[Breadth-First Search]]가 너비 방향으로 한 겹씩 탐색하는 것과 달리 깊이 방향으로 먼저 파고듭니다. 이 글에서는 DFS의 핵심 아이디어와 알고리즘, 시간·공간 복잡도, DFS의 한계, 그리고 위상 정렬·사이클 탐지 등의 활용 사례를 살펴봅니다. ## 핵심 아이디어 DFS는 미로를 탐험하는 것에 비유할 수 있다. 갈림길에서 한 방향을 선택하여 끝까지 가보고, 막다른 길에 도달하면 가장 최근의 갈림길로 되돌아와서(*backtrack*) 아직 가보지 않은 다른 길을 시도한다. 이 "되돌아오기" 동작이 DFS의 본질이며, 이는 [[Stack]]의 LIFO 특성 또는 재귀 호출의 호출 스택과 자연스럽게 대응된다. ![[dfsTraversal.svg]] 위 그래프에서 노드 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의 반복 구현에서는 같은 노드가 스택에 여러 번 들어갈 수 있으므로 꺼낼 때 처리해야 한다[^dfs-visited-timing]. ## 탐색 예시 아래 그래프에서 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 구현 ```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와 동일하게 $O(V + E)$이다. 모든 노드를 한 번씩, 모든 간선을 한 번씩 처리하기 때문이다. 공간 복잡도는 $O(V)$이다. 최악의 경우 그래프가 일직선(체인)이면 스택에 $V$개의 노드가 모두 들어갈 수 있다. 그러나 일반적으로는 BFS보다 메모리 효율이 좋다. BFS는 한 레벨의 모든 노드를 큐에 유지해야 하므로 $O(b^d)$까지 커질 수 있지만, DFS는 현재 경로의 노드만 스택에 유지하면 되므로 $O(bd)$[^dfs-space]에 그친다. ## 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. [^dfs-visited-timing]: BFS에서는 큐에 넣는 시점에 방문 처리(`visited.add`)를 해야 중복 삽입을 막을 수 있다. 반면 DFS의 반복 구현에서는 같은 노드가 스택에 여러 번 들어갈 수 있으므로, 꺼낼 때 방문 여부를 확인하여 이미 처리된 노드는 건너뛴다. [^dfs-space]: $b$는 분기 계수(*branching factor*), $d$는 탐색 깊이다. DFS는 현재 경로 위의 노드와 각 노드에서 아직 탐색하지 않은 형제 노드만 스택에 유지하면 되므로, 공간 복잡도가 $O(bd)$가 된다. Russell and Norvig (2021), Table 3.1 참조.