깊이 우선 탐색 편집하기

깊이 우선 탐색(Depth-First Search, DFS)은 그래프 또는 트리를 탐색하는 방법 중 하나로, 한 노드에서 출발하여 자식 노드를 우선 탐색한 후 더 이상 탐색할 곳이 없으면 되돌아오는 방식으로 동작한다.
==개요==
DFS는 스택(Stack) 또는 재귀(Recursion)를 사용하여 그래프의 깊은 부분을 먼저 탐색하는 전략을 따른다. 탐색 과정에서 방문한 노드를 다시 방문하지 않도록 방문 여부를 기록해야 한다.

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

=== 기본 DFS의 동작 방식 ===

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

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

==== 반복문을 이용한 DFS ====
<syntaxhighlight lang="python">
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
</syntaxhighlight>

==== 재귀를 이용한 DFS ====
<syntaxhighlight lang="python">
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
</syntaxhighlight>
==방문 상태 관리 DFS 개요==
DFS는 스택(Stack) 또는 재귀(Recursion)를 사용하여 그래프의 깊은 부분을 먼저 탐색하는 전략을 따른다. 탐색 과정에서 방문한 노드를 다시 방문하지 않도록 '''unseen''', '''seen''', '''done''' 상태를 사용하여 관리할 수 있다. 간혹 white, gray, black으로 구분하는 경우도 있기에 Three state또는 Three color DFS라고 불리기도 한다.
*'''unseen''' - 아직 방문하지 않은 노드. (white)
*'''seen''' - 방문했지만 모든 인접 노드를 탐색하지 않은 노드. (gray)
*'''done''' - 해당 노드와 모든 인접 노드의 탐색이 완료된 상태. (black)
DFS에서 노드의 방문 상태를 구분하는 이유는 다음과 같다. 

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

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

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

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

==== 반복문을 이용한 DFS ====
<syntaxhighlight lang="python">
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
</syntaxhighlight>

==== 재귀를 이용한 DFS ====
<syntaxhighlight lang="python">
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
</syntaxhighlight>

== 그 외 고급 DFS ==

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

==DFS의 시간 복잡도==
DFS의 시간 복잡도는 그래프의 정점(V)과 간선(E)의 개수에 따라 결정된다.
*'''인접 리스트(Adjacency List)'''로 구현한 경우: O(V + E)
*'''인접 행렬(Adjacency Matrix)'''로 구현한 경우: O(V²)
==DFS의 특징==
*'''경로 탐색''' - 시작점에서 목표 지점까지의 경로를 찾는 데 유용.
*'''사이클 검출''' - 방문한 노드를 다시 방문하는 경우 사이클이 존재.
*'''위상 정렬(Topological Sorting)''' - 방향 그래프에서 수행 가능.
==DFS의 활용==
*'''미로 탐색''' - 백트래킹을 활용한 최적의 경로 찾기.
*'''위상 정렬''' - DAG(Directed Acyclic Graph)에서 작업의 선후 관계를 정리.
*'''연결 요소 찾기''' - 그래프에서 연결된 컴포넌트 개수를 찾는 문제.
*'''사이클 검출''' - 그래프가 비순환적인지 확인.
==같이 보기==
*[[너비 우선 탐색]]
*[[그래프 탐색]]
*[[위상 정렬]]
*[[최단 경로 알고리즘]]