DFS(깊이 우선 탐색) 알고리즘: 동작 원리와 Python 코드 구현

깊이 우선 탐색 (DFS)란?

Depth-First Search (DFS)는 트리와 그래프 데이터 구조를 탐색하는 기본 알고리즘입니다. 각 경로를 가능한 한 깊게 탐색한 후 백트래킹하는 방식으로 동작하여 경로 찾기, 위상 정렬, 사이클 검출 등에 적합합니다.

DFS 알고리즘 설명

DFS는 재귀(암시적 호출 스택)나 명시적 스택 자료구조를 사용하여 구현할 수 있습니다. 핵심 아이디어는 다음과 같습니다:

• 루트(또는 임의의 시작 노드)에서 시작합니다.
• 노드를 방문하고 방문 표시합니다.
• 방문하지 않은 인접 노드를 재귀적 또는 반복적으로 방문합니다.

알고리즘 단계 (이진 트리 - 재귀)

1. 현재 노드를 방문합니다.
2. 왼쪽 서브트리를 재귀적으로 탐색합니다.
3. 오른쪽 서브트리를 재귀적으로 탐색합니다.

알고리즘 단계 (일반 그래프 - 스택 기반)

1. 시작 노드를 스택에 넣고 방문 표시합니다.
2. 스택이 비어있지 않은 동안:
   • 스택에서 노드를 꺼냅니다.
   • 노드를 처리합니다.
   • 방문하지 않은 인접 노드를 모두 스택에 추가하고 방문 표시합니다.

Python 예제 코드

1. 이진 트리에서 DFS (재귀)

class TreeNode:
    def __init__(self, value):
        self.val = value
        self.left = None
        self.right = None

def dfs_binary_tree(node):
    if not node:
        return
    print(node.val)
    dfs_binary_tree(node.left)
    dfs_binary_tree(node.right)

# 예제 실행
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)

dfs_binary_tree(root)

실행결과:

1
2
4
5
3

2. 일반 그래프에서 DFS (반복적)

def dfs_graph(graph, start):
    visited = set()
    stack = [start]

    while stack:
        node = stack.pop()
        if node not in visited:
            print(node)
            visited.add(node)
            for neighbor in reversed(graph[node]):
                if neighbor not in visited:
                    stack.append(neighbor)

# 예제 실행
graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['F'],
    'F': []
}

dfs_graph(graph, 'A')

실행결과:

A
B
D
E
F
C

시간 및 공간 복잡도 분석

이진 트리

• 시간 복잡도: $O(n)$ (노드 수 n 만큼 방문)
• 공간 복잡도: $O(h)$ (트리 높이 h 만큼 재귀 스택 공간 필요)

일반 그래프

• 시간 복잡도: $O(V + E)$ (정점 수 V, 간선 수 E)
• 공간 복잡도: $O(V)$ (방문한 노드 및 스택 저장용)

결론

DFS는 다양한 문제를 해결하는 데 매우 강력하고 유연한 방법입니다. 깊은 경로 탐색이나 백트래킹 기반 문제를 해결할 때 특히 효과적이며, 알고리즘 설계에 있어 필수적인 도구입니다.

참고 문헌

• Wikipedia - Depth-First Search
• GeeksforGeeks - DFS for a Graph