[python] 깊이 우선 탐색(DFS)

07 Dec 2023

python

깊이 우선 탐색(Depth-First Search, DFS)은 그래프를 탐색하는 방법 중 하나입니다. DFS는 그래프의 한 정점에서 시작하여 다음 분기로 넘어가기 전에 그래프의 깊은 부분을 탐색하는 방식입니다. 즉, 다음 분기로 넘어가기 전에 해당 분기를 완전히 탐색하는 방법입니다.

알고리즘 구현

DFS 알고리즘을 구현하기 위해서는 스택(Stack) 자료구조를 사용합니다. 아래는 Python으로 DFS 알고리즘을 구현하는 예제 코드입니다.

def dfs(graph, start_node):
    visited = []  # 방문한 노드를 저장하는 리스트
    stack = [start_node]  # 스택에 시작 노드를 넣음

    while stack:  # 스택이 비어있을 때까지 반복
        node = stack.pop()  # 스택에서 가장 위에 있는 노드를 꺼냄

        if node not in visited:
            visited.append(node)  # 방문한 노드를 저장
            stack.extend(graph[node])  # 해당 노드와 인접한 노드를 스택에 추가

    return visited

# 그래프 정의
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D'],
    'C': ['A', 'E', 'F'],
    'D': ['B'],
    'E': ['C'],
    'F': ['C']
}

# DFS 실행
result = dfs(graph, 'A')
print(result)  # ['A', 'C', 'F', 'E', 'B', 'D']

위 코드에서 dfs 함수는 graph와 start_node를 입력으로 받아서 DFS를 수행하고, 방문한 노드를 저장한 리스트 visited를 반환합니다. visited는 DFS로 탐색된 순서대로 정점을 저장하게 됩니다.

위의 예제 코드에서는 인접 리스트로 그래프를 표현하였으며, 'A' 노드로부터 DFS를 시작합니다. 결과는 ['A', 'C', 'F', 'E', 'B', 'D']와 같이 출력됩니다.

참고 자료

위키백과 - 깊이 우선 탐색