깊이 우선 탐색

깊이 우선 탐색(Depth-First Search, DFS)은 그래프 또는 트리를 탐색하는 방법 중 하나로, 한 노드에서 출발하여 자식 노드를 우선 탐색한 후 더 이상 탐색할 곳이 없으면 되돌아오는 방식으로 동작한다.

1 개요

DFS는 스택(Stack) 또는 재귀(Recursion)를 사용하여 그래프의 깊은 부분을 먼저 탐색하는 전략을 따른다. 탐색 과정에서 방문한 노드를 다시 방문하지 않도록 방문 여부를 기록해야 한다.

2 기본 DFS

단순히 모든 노드를 방문하기 위한 목적으로, 가장 간단하게 구현한 DFS를 의미한다.

2.1 기본 DFS의 동작 방식

1. 시작 노드를 방문하고 스택에 넣는다.
2. 스택의 최상단 노드에서 방문하지 않은 인접 노드를 찾는다.
3. 방문하지 않은 노드가 있으면 해당 노드를 방문하고 스택에 넣는다.
4. 방문하지 않은 노드가 없으면 스택에서 노드를 제거하며 백트래킹(Backtracking)한다.
5. 스택이 비어 있으면 탐색이 종료된다.

2.2 기본 DFS의 구현

DFS는 스택을 명시적으로 사용하는 반복문 방식과, 함수 호출 스택을 활용하는 재귀 방식으로 구현할 수 있다.

2.2.1 반복문을 이용한 DFS

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

    while stack:
        node = stack.pop()
        if node not in visited:
            visited.add(node)
            print(node, end=" ")

            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_iterative(graph, 'A')
# 출력: A C F B E D

2.2.2 재귀를 이용한 DFS

def dfs_recursive(graph, node, visited=None):
    if visited is None:
        visited = set()

    if node not in visited:
        visited.add(node)
        print(node, end=" ")

        for neighbor in graph[node]:
            dfs_recursive(graph, neighbor, visited)

# 그래프 표현 (인접 리스트)
graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['F'],
    'F': []
}

dfs_recursive(graph, 'A')
# 출력: A B D E F C

3 방문 상태 관리 DFS 개요

DFS는 스택(Stack) 또는 재귀(Recursion)를 사용하여 그래프의 깊은 부분을 먼저 탐색하는 전략을 따른다. 탐색 과정에서 방문한 노드를 다시 방문하지 않도록 unseen, seen, done 상태를 사용하여 관리할 수 있다. 간혹 white, gray, black으로 구분하는 경우도 있기에 Three state또는 Three color DFS라고 불리기도 한다.

• unseen - 아직 방문하지 않은 노드. (white)
• seen - 방문했지만 모든 인접 노드를 탐색하지 않은 노드. (gray)
• done - 해당 노드와 모든 인접 노드의 탐색이 완료된 상태. (black)

DFS에서 노드의 방문 상태를 구분하는 이유는 다음과 같다.

• 사이클 방지 - 방문한 노드를 다시 방문하는 경우 무한 루프 발생 가능.
• 중복 탐색 방지 - 이미 처리한 노드를 다시 탐색하지 않도록 함.
• 위상 정렬(Topological Sorting) - 선후 관계를 유지하며 그래프를 정렬할 때 유용.

3.1 방문 상태 관리 DFS의 동작 방식

1. 시작 노드를 seen 상태로 설정하고 스택에 넣는다.
2. 스택의 최상단 노드를 확인하고 방문하지 않은 인접 노드를 찾는다.
3. 방문하지 않은 노드가 있으면 해당 노드를 seen으로 설정하고 스택에 추가한다.
4. 더 이상 탐색할 노드가 없으면 스택에서 제거하며 해당 노드를 done으로 변경한다.
5. 스택이 비어 있으면 탐색이 종료된다.

3.2 방문 상태 관리 DFS의 구현

DFS는 스택을 명시적으로 사용하는 반복문 방식과, 함수 호출 스택을 활용하는 재귀 방식으로 구현할 수 있다.

3.2.1 반복문을 이용한 DFS

def dfs_iterative(graph, start):
    stack = [start]
    state = {node: "unseen" for node in graph}
    state[start] = "seen"

    while stack:
        node = stack[-1]  # 스택의 최상단 노드 확인

        # 방문하지 않은 인접 노드 찾기
        unvisited_neighbors = [neighbor for neighbor in graph[node] if state[neighbor] == "unseen"]

        if unvisited_neighbors:
            next_node = unvisited_neighbors[0]
            state[next_node] = "seen"
            stack.append(next_node)
        else:
            state[node] = "done"
            stack.pop()
            print(node, end=" ")  # 탐색 완료된 노드 출력

# 그래프 표현 (인접 리스트)
graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['F'],
    'F': []
}

dfs_iterative(graph, 'A')
# 출력: D E B F C A

3.2.2 재귀를 이용한 DFS

def dfs_recursive(graph, node, state=None):
    if state is None:
        state = {n: "unseen" for n in graph}

    state[node] = "seen"

    for neighbor in graph[node]:
        if state[neighbor] == "unseen":
            dfs_recursive(graph, neighbor, state)

    state[node] = "done"
    print(node, end=" ")  # 탐색 완료된 노드 출력

# 그래프 표현 (인접 리스트)
graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['F'],
    'F': []
}

dfs_recursive(graph, 'A')
# 출력: D E B F C A

4 그 외 고급 DFS

• 타임스탬프 및 간선 분류를 추가하고 싸이클 검출, 위상 정렬, SCC 찾기 등 더 강력한 DFS를 사용하기도 한다.
• 타임스탬프 깊이 우선 탐색 참고

5 DFS의 시간 복잡도

DFS의 시간 복잡도는 그래프의 정점(V)과 간선(E)의 개수에 따라 결정된다.

• 인접 리스트(Adjacency List)로 구현한 경우: O(V + E)
• 인접 행렬(Adjacency Matrix)로 구현한 경우: O(V²)

6 DFS의 특징

• 경로 탐색 - 시작점에서 목표 지점까지의 경로를 찾는 데 유용.
• 사이클 검출 - 방문한 노드를 다시 방문하는 경우 사이클이 존재.
• 위상 정렬(Topological Sorting) - 방향 그래프에서 수행 가능.

7 DFS의 활용

• 미로 탐색 - 백트래킹을 활용한 최적의 경로 찾기.
• 위상 정렬 - DAG(Directed Acyclic Graph)에서 작업의 선후 관계를 정리.
• 연결 요소 찾기 - 그래프에서 연결된 컴포넌트 개수를 찾는 문제.
• 사이클 검출 - 그래프가 비순환적인지 확인.

8 같이 보기

• 너비 우선 탐색
• 그래프 탐색
• 위상 정렬
• 최단 경로 알고리즘