깊이 우선 탐색 편집하기 (부분)

==방문 상태 관리 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>