깊이 우선 탐색

작성자

익명

작성일

2026.07.10

조회수

버전

깊이 우선 탐색 DFS 그래프 알고리즘 백트래킹 스택 재귀 함수 시간 복잡도 Python 초급

깊이 우선 탐색 (Depth-First Search, DFS)

1. 개요

깊이 우선 탐색(Depth-First Search, DFS)은 그래프나 트리 구조에서 루트 노드(혹은 임의의 시작 노드)에서 시작하여 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 깊이 중심의 그래프 탐색 알고리즘입니다.

DFS는 한 방향으로 갈 수 있을 때까지 최대한 깊게 탐색하다가, 더 이상 갈 곳이 없으면 가장 최근에 방문했던 갈림길로 되돌아와(Backtracking) 다른 방향을 탐색하는 방식으로 동작합니다.

2. 동작 원리 및 과정

DFS의 핵심은 '최대한 깊게'와 '되돌아오기'입니다. 이를 위해 후입선출(LIFO, Last-In-First-Out) 구조인 스택(Stack) 자료구조를 사용하거나, 시스템 스택을 이용하는 재귀 함수(Recursion) 형태로 구현합니다.

탐색 과정

탐색 시작 노드를 방문 처리하고 스택에 삽입하거나 재귀 함수를 호출합니다.
현재 노드에 연결된 인접 노드 중 방문하지 않은 노드가 있는지 확인합니다.
방문하지 않은 인접 노드가 있다면, 해당 노드를 방문 처리하고 스택에 삽입하거나 재귀 함수를 호출한 뒤 2번 과정으로 돌아갑니다.
방문하지 않은 인접 노드가 없다면, 스택에서 현재 노드를 꺼내고(Pop) 이전 노드로 되돌아갑니다.
스택이 빌 때까지 위 과정을 반복합니다.

[여기에 DFS 탐색 순서를 보여주는 트리/그래프 다이어그램 삽입 필요]

방문 처리(Visited)의 중요성

그래프에는 사이클(Cycle, 경로를 따라갔을 때 다시 시작점으로 돌아오는 경로)이 존재할 수 있습니다. 방문 처리를 하지 않을 경우, 알고리즘이 동일한 노드를 무한히 반복해서 방문하는 무한 루프(Infinite Loop)에 빠지게 되므로, 반드시 visited 배열이나 셋(Set)을 통해 방문 여부를 기록해야 합니다.

3. 알고리즘 구현

DFS는 구현 방식에 따라 재귀 방식과 명시적 스택 방식으로 나뉩니다.

3.1 재귀(Recursion) 방식

가장 일반적인 구현 방법으로, 코드가 간결하며 백트래킹 구현이 용이합니다.

def dfs_recursive(graph, v, visited):
    # 현재 노드를 방문 처리
    visited[v] = True
    print(v, end=' ')
    
    # 현재 노드와 연결된 다른 노드를 재귀적으로 방문
    for i in graph[v]:
        if not visited[i]:
            dfs_recursive(graph, i, visited)

# 그래프 예시 (인접 리스트)
graph = [[], [2, 3, 8], [1, 7], [1, 4, 5], [3, 5], [3, 4], [6], [2], [1]]
visited = [False] * 9
dfs_recursive(graph, 1, visited)

3.2 명시적 스택(Stack) 방식

재귀 깊이 제한 문제를 피하기 위해 list나 deque를 사용하여 직접 스택을 구현하는 방식입니다.

def dfs_stack(graph, start_node):
    visited = [False] * len(graph)
    stack = [start_node]
    
    while stack:
        v = stack.pop()
        if not visited[v]:
            visited[v] = True
            print(v, end=' ')
            # 인접 노드가 오름차순으로 정렬되어 있을 때, 
            # 스택의 LIFO 특성상 역순으로 넣어야 작은 번호부터 방문하게 됩니다.
            for i in reversed(graph[v]):
                if not visited[i]:
                    stack.append(i)

4. 시간 및 공간 복잡도

DFS의 복잡도는 그래프를 표현하는 방식(인접 행렬 vs 인접 리스트)에 따라 달라집니다.

구분	시간 복잡도	그래프 저장 공간	비고
인접 행렬	$O(V^2)$	$O(V^2)$	모든 정점 쌍을 확인해야 함
인접 리스트	$O(V + E)$	$O(V + E)$	연결된 간선만 확인함

$V$: 정점(Vertex)의 수
$E$: 간선(Edge)의 수
추가 공간 복잡도: 알고리즘 수행을 위한 추가 공간 복잡도는 최악의 경우(편향 트리 등) 재귀 깊이가 $V$까지 깊어질 수 있어 $O(V)$의 스택 공간이 필요합니다.

5. 장단점

장점

메모리 효율: BFS에 비해 일반적으로 더 적은 메모리를 사용합니다. (특히 너비가 넓은 그래프에서 유리)
목표 노드의 깊이가 깊은 경우: 목표 노드가 깊은 곳에 위치한다면 BFS보다 빠르게 찾을 수 있습니다.
경로 탐색: 경로의 특징을 저장하며 탐색하기에 용이하여 백트래킹 알고리즘의 기초가 됩니다.

단점

최단 경로 보장 불가: 처음 발견한 경로가 최단 경로라는 보장이 없습니다.
무한 루프 위험: 방문 처리를 누락하거나 사이클이 있는 그래프에서 잘못 구현할 경우 무한 루프에 빠질 수 있습니다.
재귀 깊이 제한: 시스템의 재귀 호출 한계로 인해 런타임 에러(Stack Overflow)가 발생할 수 있습니다.

6. 재귀 깊이 제한 해결 방법

Python과 같은 언어는 기본 재귀 깊이 제한(보통 1,000회)이 설정되어 있어, 정점의 수가 많은 그래프에서는 RecursionError가 발생합니다. 이를 해결하는 방법은 다음과 같습니다.

재귀 한도 강제 상향: sys.setrecursionlimit() 함수를 사용하여 제한을 늘립니다.
```
   import sys
   sys.setrecursionlimit(10**6) # 100만 회로 상향
   
```
반복문 기반 구현: 재귀 대신 명시적 스택(Stack)을 사용하여 루프 형태로 구현합니다.

7. 활용 사례 및 응용

경로 찾기: 두 노드 사이에 경로가 존재하는지 확인하는 문제.
사이클 검출: 무방향 그래프나 방향 그래프에서 사이클이 존재하는지 확인.
위상 정렬(Topological Sort): 방향 그래프의 정점들을 선행 순서에 따라 나열할 때 사용.
미로 찾기: 한 길을 끝까지 가보고 막히면 되돌아오는 미로 탐색 문제. (예: 막다른 길에 도달할 때까지 전진하다가 벽을 만나면 이전 갈림길로 돌아가 다른 경로 탐색)
연결 요소(Connected Component) 찾기: 그래프 내에서 서로 연결된 정점들의 묶음을 찾는 문제.

8. BFS(너비 우선 탐색)와의 비교

비교 항목	깊이 우선 탐색 (DFS)	너비 우선 탐색 (BFS)
탐색 방식	최대한 깊이 탐색 후 후퇴	인접한 노드부터 모두 탐색 후 확장
사용 자료구조	스택(Stack), 재귀 함수	큐(Queue)
최단 경로 보장	보장하지 않음	보장함 (가중치 없는 그래프)
메모리 사용	상대적으로 적음	상대적으로 많음 (큐에 많은 노드 저장)
주요 용도	모든 경로 탐색, 사이클 검출, 백트래킹	최단 거리 찾기, 레벨 단위 탐색

9. 실제 문제 풀이 적용 팁

최단 거리 문제인가? $\rightarrow$ 그렇다면 DFS보다는 BFS를 우선 고려하십시오.
모든 경우의 수를 탐색해야 하는가? $\rightarrow$ 조합, 순열, 모든 경로 탐색 문제라면 DFS(백트래킹)가 적합합니다.
그래프의 규모가 큰가? $\rightarrow$ 정점의 개수가 $10^4$개 이상이라면 재귀 방식보다는 스택 방식을 사용하거나 setrecursionlimit을 반드시 설정하십시오.
방문 처리 시점: 재귀 호출 직후에 방문 처리를 하는지, 호출 전에 하는지에 따라 탐색 순서와 결과가 달라질 수 있으므로 일관성을 유지하십시오.

📝 마크다운 원본

이 문서의 마크다운 원본 내용입니다.

# 깊이 우선 탐색 (Depth-First Search, DFS)

## 1. 개요
깊이 우선 탐색(Depth-First Search, DFS)은 그래프나 트리 구조에서 루트 노드(혹은 임의의 시작 노드)에서 시작하여 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 깊이 중심의 그래프 탐색 알고리즘입니다.

DFS는 한 방향으로 갈 수 있을 때까지 최대한 깊게 탐색하다가, 더 이상 갈 곳이 없으면 가장 최근에 방문했던 갈림길로 되돌아와(Backtracking) 다른 방향을 탐색하는 방식으로 동작합니다.

## 2. 동작 원리 및 과정
DFS의 핵심은 **'최대한 깊게'**와 **'되돌아오기'**입니다. 이를 위해 후입선출(LIFO, Last-In-First-Out) 구조인 **스택(Stack)** 자료구조를 사용하거나, 시스템 스택을 이용하는 **재귀 함수(Recursion)** 형태로 구현합니다.

### 탐색 과정
1. 탐색 시작 노드를 방문 처리하고 스택에 삽입하거나 재귀 함수를 호출합니다.
2. 현재 노드에 연결된 인접 노드 중 방문하지 않은 노드가 있는지 확인합니다.
3. 방문하지 않은 인접 노드가 있다면, 해당 노드를 방문 처리하고 스택에 삽입하거나 재귀 함수를 호출한 뒤 2번 과정으로 돌아갑니다.
4. 방문하지 않은 인접 노드가 없다면, 스택에서 현재 노드를 꺼내고(Pop) 이전 노드로 되돌아갑니다.
5. 스택이 빌 때까지 위 과정을 반복합니다.

`[여기에 DFS 탐색 순서를 보여주는 트리/그래프 다이어그램 삽입 필요]`

### 방문 처리(Visited)의 중요성
그래프에는 사이클(Cycle, 경로를 따라갔을 때 다시 시작점으로 돌아오는 경로)이 존재할 수 있습니다. 방문 처리를 하지 않을 경우, 알고리즘이 동일한 노드를 무한히 반복해서 방문하는 **무한 루프(Infinite Loop)**에 빠지게 되므로, 반드시 `visited` 배열이나 셋(Set)을 통해 방문 여부를 기록해야 합니다.

## 3. 알고리즘 구현
DFS는 구현 방식에 따라 재귀 방식과 명시적 스택 방식으로 나뉩니다.

### 3.1 재귀(Recursion) 방식
가장 일반적인 구현 방법으로, 코드가 간결하며 백트래킹 구현이 용이합니다.

```python
def dfs_recursive(graph, v, visited):
    # 현재 노드를 방문 처리
    visited[v] = True
    print(v, end=' ')
    
    # 현재 노드와 연결된 다른 노드를 재귀적으로 방문
    for i in graph[v]:
        if not visited[i]:
            dfs_recursive(graph, i, visited)

# 그래프 예시 (인접 리스트)
graph = [[], [2, 3, 8], [1, 7], [1, 4, 5], [3, 5], [3, 4], [6], [2], [1]]
visited = [False] * 9
dfs_recursive(graph, 1, visited)
```

### 3.2 명시적 스택(Stack) 방식
재귀 깊이 제한 문제를 피하기 위해 `list`나 `deque`를 사용하여 직접 스택을 구현하는 방식입니다.

```python
def dfs_stack(graph, start_node):
    visited = [False] * len(graph)
    stack = [start_node]
    
    while stack:
        v = stack.pop()
        if not visited[v]:
            visited[v] = True
            print(v, end=' ')
            # 인접 노드가 오름차순으로 정렬되어 있을 때, 
            # 스택의 LIFO 특성상 역순으로 넣어야 작은 번호부터 방문하게 됩니다.
            for i in reversed(graph[v]):
                if not visited[i]:
                    stack.append(i)
```

## 4. 시간 및 공간 복잡도
DFS의 복잡도는 그래프를 표현하는 방식(인접 행렬 vs 인접 리스트)에 따라 달라집니다.

| 구분 | 시간 복잡도 | 그래프 저장 공간 | 비고 |
| :--- | :--- | :--- | :--- |
| **인접 행렬** | $O(V^2)$ | $O(V^2)$ | 모든 정점 쌍을 확인해야 함 |
| **인접 리스트** | $O(V + E)$ | $O(V + E)$ | 연결된 간선만 확인함 |

- $V$: 정점(Vertex)의 수
- $E$: 간선(Edge)의 수
- **추가 공간 복잡도**: 알고리즘 수행을 위한 추가 공간 복잡도는 최악의 경우(편향 트리 등) 재귀 깊이가 $V$까지 깊어질 수 있어 $O(V)$의 스택 공간이 필요합니다.

## 5. 장단점
### 장점
- **메모리 효율**: BFS에 비해 일반적으로 더 적은 메모리를 사용합니다. (특히 너비가 넓은 그래프에서 유리)
- **목표 노드의 깊이가 깊은 경우**: 목표 노드가 깊은 곳에 위치한다면 BFS보다 빠르게 찾을 수 있습니다.
- **경로 탐색**: 경로의 특징을 저장하며 탐색하기에 용이하여 백트래킹 알고리즘의 기초가 됩니다.

### 단점
- **최단 경로 보장 불가**: 처음 발견한 경로가 최단 경로라는 보장이 없습니다.
- **무한 루프 위험**: 방문 처리를 누락하거나 사이클이 있는 그래프에서 잘못 구현할 경우 무한 루프에 빠질 수 있습니다.
- **재귀 깊이 제한**: 시스템의 재귀 호출 한계로 인해 런타임 에러(Stack Overflow)가 발생할 수 있습니다.

## 6. 재귀 깊이 제한 해결 방법
Python과 같은 언어는 기본 재귀 깊이 제한(보통 1,000회)이 설정되어 있어, 정점의 수가 많은 그래프에서는 `RecursionError`가 발생합니다. 이를 해결하는 방법은 다음과 같습니다.

1. **재귀 한도 강제 상향**: `sys.setrecursionlimit()` 함수를 사용하여 제한을 늘립니다.
   ```python
   import sys
   sys.setrecursionlimit(10**6) # 100만 회로 상향
   ```
2. **반복문 기반 구현**: 재귀 대신 명시적 스택(Stack)을 사용하여 루프 형태로 구현합니다.

## 7. 활용 사례 및 응용
- **경로 찾기**: 두 노드 사이에 경로가 존재하는지 확인하는 문제.
- **사이클 검출**: 무방향 그래프나 방향 그래프에서 사이클이 존재하는지 확인.
- **위상 정렬(Topological Sort)**: 방향 그래프의 정점들을 선행 순서에 따라 나열할 때 사용.
- **미로 찾기**: 한 길을 끝까지 가보고 막히면 되돌아오는 미로 탐색 문제. (예: 막다른 길에 도달할 때까지 전진하다가 벽을 만나면 이전 갈림길로 돌아가 다른 경로 탐색)
- **연결 요소(Connected Component) 찾기**: 그래프 내에서 서로 연결된 정점들의 묶음을 찾는 문제.

## 8. BFS(너비 우선 탐색)와의 비교

| 비교 항목 | 깊이 우선 탐색 (DFS) | 너비 우선 탐색 (BFS) |
| :--- | :--- | :--- |
| **탐색 방식** | 최대한 깊이 탐색 후 후퇴 | 인접한 노드부터 모두 탐색 후 확장 |
| **사용 자료구조** | 스택(Stack), 재귀 함수 | 큐(Queue) |
| **최단 경로 보장** | 보장하지 않음 | **보장함** (가중치 없는 그래프) |
| **메모리 사용** | 상대적으로 적음 | 상대적으로 많음 (큐에 많은 노드 저장) |
| **주요 용도** | 모든 경로 탐색, 사이클 검출, 백트래킹 | 최단 거리 찾기, 레벨 단위 탐색 |

## 9. 실제 문제 풀이 적용 팁
1. **최단 거리 문제인가?** $\rightarrow$ 그렇다면 DFS보다는 **BFS**를 우선 고려하십시오.
2. **모든 경우의 수를 탐색해야 하는가?** $\rightarrow$ 조합, 순열, 모든 경로 탐색 문제라면 **DFS(백트래킹)**가 적합합니다.
3. **그래프의 규모가 큰가?** $\rightarrow$ 정점의 개수가 $10^4$개 이상이라면 재귀 방식보다는 **스택 방식**을 사용하거나 `setrecursionlimit`을 반드시 설정하십시오.
4. **방문 처리 시점**: 재귀 호출 직후에 방문 처리를 하는지, 호출 전에 하는지에 따라 탐색 순서와 결과가 달라질 수 있으므로 일관성을 유지하십시오.

AI 생성 콘텐츠 안내

이 문서는 AI 모델(gemma-4-31b)에 의해 생성된 콘텐츠입니다.

주의사항: AI가 생성한 내용은 부정확하거나 편향된 정보를 포함할 수 있습니다. 중요한 결정을 내리기 전에 반드시 신뢰할 수 있는 출처를 통해 정보를 확인하시기 바랍니다.

위키너와나