[파이썬] DFS 구현

DFS는 깊이 우선 탐색(Depth First Search)의 약자입니다. 이는 그래프에서 모든 노드를 탐색하는 알고리즘 중 하나입니다. 그래프는 노드와 간선으로 구성되며, 간선은 노드와 노드를 연결하는 경로를 나타냅니다. DFS는 특정 노드에서 시작하여 그래프의 모든 노드를 방문하며, 이때 방문한 노드는 스택(stack)에 저장됩니다.

파이썬으로 DFS를 구현할 때에는 일반적으로 재귀 함수(recursive function)를 사용합니다. 이때, 방문한 노드를 저장하기 위해 스택 대신에 파이썬의 리스트(list)를 사용할 수 있습니다.

1. 재귀함수로 구현

 

# 그래프를 인접 리스트로 구현한 예시입니다.
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

# DFS 함수를 정의합니다.
def dfs(graph, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)
    print(start, end=' ')
    for next_node in graph[start]:
        if next_node not in visited:
            dfs(graph, next_node, visited)

# DFS를 호출합니다.
dfs(graph, 'A')

위 코드에서 dfs 함수는 graph와 start를 인자로 받습니다. visited는 이전에 방문한 노드를 저장하기 위한 매개변수입니다. 함수가 처음 호출될 때는 visited가 None으로 초기화되며, 이후에는 방문한 노드를 visited에 추가합니다. 그리고 현재 노드를 출력한 후, 다음 노드를 재귀적으로 호출합니다. 이때, 다음 노드가 이미 visited에 포함되어 있으면 재귀 호출을 하지 않습니다.

위 코드의 출력 결과는 다음과 같습니다.

 

A B D E F C

위 출력 결과에서 볼 수 있듯이, DFS는 한 노드에서 시작하여 그래프의 모든 노드를 탐색하는데 있어서 깊이 방향으로 탐색을 진행합니다. 따라서, A부터 B까지 탐색하고, B의 인접 노드인 D와 E를 탐색한 후, E의 인접 노드인 F를 탐색하고 다시 B로 돌아와 B의 다른 인접 노드인 A를 탐색하고, 이렇게 진행됩니다.

 

2. 스택(stack)을 사용하여 구현

 

스택을 사용하는 방법은 반복문을 사용하여 구현하며, 재귀함수를 사용하는 방법과 유사한 원리로 동작합니다.

 

# 그래프를 인접 리스트로 구현한 예시입니다.
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

# DFS 함수를 정의합니다.
def dfs(graph, start):
    visited = set()  # 방문한 노드를 저장할 set
    stack = [start]  # 시작 노드를 스택에 추가
    while stack:
        node = stack.pop()  # 스택에서 가장 최근에 추가된 노드를 가져옴
        if node not in visited:
            visited.add(node)  # 방문한 노드를 저장
            print(node, end=' ')
            for next_node in graph[node]:
                if next_node not in visited:
                    stack.append(next_node)  # 다음에 방문할 노드를 스택에 추가

# DFS를 호출합니다.
dfs(graph, 'A')

위 코드에서 dfs 함수는 graph와 start를 인자로 받습니다. visited는 이전에 방문한 노드를 저장하기 위한 set이며, stack은 방문할 노드를 저장하기 위한 리스트입니다. 함수는 stack이 비어있을 때까지 반복하며, 스택에서 가장 최근에 추가된 노드를 가져옵니다. 이때, 가져온 노드가 visited에 포함되어 있지 않으면 방문한 노드로 처리한 후, 인접 노드를 스택에 추가합니다. 이렇게 스택을 사용하여 DFS를 구현할 경우, 재귀함수를 사용하는 방법과 같은 결과를 얻을 수 있습니다.