[파이썬] BFS 예제 코드

BFS(Breadth-First Search)는 그래프에서 너비 우선 탐색을 수행하는 알고리즘으로, 특정 노드에서 시작하여 인접한 노드를 모두 방문한 후에 다음 노드로 이동하는 방식으로 탐색합니다. 즉, 가까운 노드부터 탐색을 시작하여 먼 노드로 이동하며 탐색합니다. BFS는 주로 최단 경로를 찾는 문제에서 사용됩니다.

 

BFS 알고리즘은 큐(Queue) 자료구조를 사용하여 구현할 수 있습니다. 먼저 탐색을 시작하는 노드를 큐에 삽입합니다. 그리고 큐에서 하나의 노드를 꺼내서 해당 노드의 인접한 노드들을 모두 큐에 삽입합니다. 이 때, 이미 방문한 노드를 다시 큐에 삽입하지 않도록 방문한 노드를 체크해야 합니다. 큐가 빌 때까지 이 과정을 반복하며 모든 노드를 탐색합니다.

 

1. 예제 코드

 

아래는 Python으로 구현된 BFS 예제 코드입니다. 이 코드는 무방향 그래프에서 BFS를 수행하는 코드입니다.

 

from collections import deque

def bfs(graph, start_node):
    visited = []
    queue = deque([start_node])

    while queue:
        node = queue.popleft()
        if node not in visited:
            visited.append(node)
            queue.extend(graph[node])

    return visited

# 그래프 정보
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D'],
    'C': ['A', 'G', 'H', 'I'],
    'D': ['B', 'E', 'F'],
    'E': ['D'],
    'F': ['D'],
    'G': ['C'],
    'H': ['C'],
    'I': ['C', 'J'],
    'J': ['I']
}

print(bfs(graph, 'A')) # ['A', 'B', 'C', 'D', 'G', 'H', 'I', 'E', 'F', 'J']

위 코드에서, graph 변수는 그래프 정보를 나타내는 딕셔너리입니다. 딕셔너리의 각 키는 노드를 나타내며, 해당 키에 대한 값은 인접한 노드들의 리스트입니다.

bfs 함수에서는 visited 리스트와 queue 변수를 초기화합니다. visited 리스트는 방문한 노드를 저장하는 리스트이며, queue 변수는 BFS 알고리즘에서 사용하는 큐 자료구조입니다. queue 변수는 collections 모듈의 deque 클래스를 사용하여 초기화합니다.

while문에서는 큐가 빌 때까지 반복하며, 큐에서 하나의 노드를 꺼내서 해당 노드의 인접한 노드들을 모두 큐에 삽입합니다. 이 때, 이미 방문한 노드를 다시 큐에 삽입하지 않도록 방문한 노드를 체크합니다. 방문한 노드는 visited 리스트에 추가합니다.

while문을 모두 수행한 후에는 visited 리스트를 반환합니다. 이 리스트는 BFS 알고리즘을 수행한 결과로, 시작 노드부터 가까운 순서대로 탐색한 노드들의 리스트입니다.

위 코드에서는 그래프가 딕셔너리로 구현되어 있지만, 다른 자료구조로 구현된 그래프에서도 크게 다르지 않은 방식으로 BFS를 구현할 수 있습니다. 단, 큐 자료구조는 반드시 사용해야 합니다.