[알고리즘] DFS (깊이 우선 탐색, Depth-First Search)

DFS는 그래프나 트리를 탐색하는 알고리즘 중 하나로, 한 노드를 선택한 후 최대한 깊이 탐색한 후 다시 돌아오는 방식으로 작동한다. DFS는 재귀(recursion) 또는 스택(stack) 을 사용하여 구현할 수 있다.

시작 노드부터 탐색을 시작
현재 노드를 방문하고 방문 기록을 남김
인접한 노드 중 아직 방문하지 않은 노드가 있으면 그 노드로 이동
더 이상 방문할 노드가 없으면 이전 노드로 돌아감 (백트래킹)
모든 노드를 탐색할 때까지 반복

1. 트리의 레벨 순회(DFS)

print(root.value)의 위치에 따라 트리 순회의 방식이 달라진다. DFS(깊이 우선 탐색) 알고리즘에서 트리 순회는 노드를 방문하는 순서에 따라 전위 순회(Pre-order), 중위 순회(In-order), 후위 순회(Post-order)로 구분한다.

1) 전위 순회 (Pre-order Traversal)

전위 순회는 노드 -> 왼쪽 자식 -> 오른쪽 자식 순으로 탐색한다. print(root.value)를 노드를 먼저 방문하는 부분에 위치시킴

def pre_order_traversal(root):
    if root is None:
        return
    print(root.value)  # 노드를 먼저 방문
    pre_order_traversal(root.left)  # 왼쪽 자식 탐색
    pre_order_traversal(root.right)  # 오른쪽 자식 탐색

2) 중위 순회 (In-order Traversal)

중위 순회는 왼쪽 자식 -> 노드 -> 오른쪽 자식 순으로 탐색한다. print(root.value)는 왼쪽 자식을 모두 방문한 후, 현재 노드를 방문하는 부분에 위치함

def in_order_traversal(root):
    if root is None:
        return
    in_order_traversal(root.left)  # 왼쪽 자식 탐색
    print(root.value)  # 노드를 방문
    in_order_traversal(root.right)  # 오른쪽 자식 탐색

3) 후위 순회 (Post-order Traversal)

후위 순회는 왼쪽 자식 -> 오른쪽 자식 -> 노드 순으로 탐색한다. print(root.value)는 두 자식을 모두 방문한 후, 마지막에 노드를 방문하는 부분에 위치함

def post_order_traversal(root):
    if root is None:
        return
    post_order_traversal(root.left)  # 왼쪽 자식 탐색
    post_order_traversal(root.right)  # 오른쪽 자식 탐색
    print(root.value)  # 노드를 마지막에 방문

4) 정리

전위 순회 (Pre-order): print(root.value)는 자기 자신을 먼저 방문하는 시점에 넣는다.
중위 순회 (In-order): print(root.value)는 왼쪽 자식 탐색 후 현재 노드를 방문하는 시점에 넣는다.
후위 순회 (Post-order): print(root.value)는 왼쪽, 오른쪽 자식 탐색 후 현재 노드를 방문하는 시점에 넣는다.

즉, print(root.value)가 트리를 탐색하는 순서에 중요한 영향을 미치며, 트리 순회 방법을 정의하는 핵심적인 부분이다.

2. 그래프 탐색 DFS 코드 예제

1) 재귀(Recursion) 방식

def dfs_recursive(node, visited, graph):
    """DFS를 재귀 방식으로 구현"""
    visited.add(node)  # 현재 노드를 방문 처리
    print(node, end=" ")  # 방문한 노드 출력

    for neighbor in graph[node]:  # 현재 노드와 연결된 노드 탐색
        if neighbor not in visited:  # 방문하지 않은 노드라면 재귀 호출
            dfs_recursive(neighbor, visited, graph)

# 그래프 예제 (인접 리스트 방식)
graph = {
    0: [1, 2],
    1: [0, 3, 4],
    2: [0, 5, 6],
    3: [1],
    4: [1],
    5: [2],
    6: [2]
}

visited = set()  # 방문한 노드를 저장할 집합
dfs_recursive(0, visited, graph)  # 0번 노드에서 시작

재귀 방식의 특징

코드가 간결하고 직관적
하지만 재귀 호출이 깊어지면 스택 오버플로우(Stack Overflow) 가 발생할 수 있음
트리 구조 탐색에 유용함

2) 스택(Stack) 방식

def dfs_stack(start, graph):
    """DFS를 스택을 사용하여 구현"""
    visited = set()  # 방문한 노드를 저장할 집합
    stack = [start]  # 시작 노드를 스택에 추가

    while stack:  # 스택이 비어있지 않으면 계속 실행
        node = stack.pop()  # 스택에서 노드를 꺼냄
        if node not in visited:  # 방문하지 않았다면
            visited.add(node)  # 방문 처리
            print(node, end=" ")  # 방문한 노드 출력

            # 인접 노드를 역순으로 스택에 추가 (순서 보장을 위해)
            stack.extend(reversed(graph[node]))  

# 그래프 예제 (인접 리스트 방식)
graph = {
    0: [1, 2],
    1: [0, 3, 4],
    2: [0, 5, 6],
    3: [1],
    4: [1],
    5: [2],
    6: [2]
}

dfs_stack(0, graph)  # 0번 노드에서 시작

스택 방식의 특징

반복문을 사용하여 재귀의 한계를 극복할 수 있음
명시적으로 스택을 사용하기 때문에 스택 오버플로우를 방지할 수 있음
하지만 코드가 재귀 방식보다 약간 복잡해질 수 있음

3. DFS vs BFS 비교

DFS (깊이 우선 탐색)	BFS (너비 우선 탐색)
탐색 방식	한 방향으로 끝까지 탐색 후 백트래킹
자료 구조	스택(Stack) / 재귀(Recursion)
특징	백트래킹에 유리, 경로 탐색 문제에 적합
시간 복잡도	O(V + E)
공간 복잡도	O(V) (재귀 깊이)

DFS는 백트래킹 문제 (예: 미로 탐색, 순열 생성, 그래프 경로 탐색) 등에 자주 사용됨
BFS는 최단 경로 탐색 (예: 최단 거리 문제, 네트워크 탐색) 등에 자주 사용됨