[파이썬] 너비 우선 탐색 (BFS)의 개념과 구현

04 Sep 2023

python

너비 우선 탐색 (BFS, Breadth-First Search)은 그래프를 탐색하는 기법 중 하나로, 시작 정점에서 가까운 정점부터 순서대로 방문하는 탐색 알고리즘입니다. BFS는 큐 (Queue) 자료 구조를 활용하여 구현할 수 있습니다.

개념

BFS는 시작 정점을 큐에 넣고, 해당 정점과 연결된 모든 인접 정점들을 큐에 넣은 후, 하나씩 꺼내어 방문하는 방식으로 동작합니다. 이러한 방식을 사용하면, 시작 정점으로부터의 거리가 가까운 정점들부터 방문하므로, 최단 경로를 찾는 데에 유용합니다.

BFS의 동작 과정은 다음과 같습니다.

시작 노드를 큐에 넣습니다.
큐에서 노드를 하나 꺼내어 방문합니다.
해당 노드와 연결된 인접 노드들을 모두 큐에 넣습니다.
큐가 비어질 때까지 2, 3번 과정을 반복합니다.

구현

이제 파이썬으로 BFS를 구현해보겠습니다. 아래는 간단한 그래프를 사용하여 BFS를 구현하는 예시입니다.

from collections import deque

def bfs(graph, start):
    visited = set()  # 방문한 노드를 저장하기 위한 집합
    queue = deque([start])  # 탐색을 위한 큐
    visited.add(start)  # 시작 노드를 방문한 것으로 처리

    while queue:
        node = queue.popleft()  # 큐에서 노드를 하나 꺼냄
        print(node, end=' ')  # 노드 출력

        # 해당 노드와 연결된 인접 노드들을 방문하기 위해 큐에 추가
        for neighbor in graph[node]:
            if neighbor not in visited:
                queue.append(neighbor)
                visited.add(neighbor)

# 예시 그래프
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D'],
    'C': ['A', 'G', 'H'],
    'D': ['B', 'E', 'F'],
    'E': ['D'],
    'F': ['D'],
    'G': ['C'],
    'H': ['C']
}

# BFS 실행
print("BFS 탐색 순서:")
bfs(graph, 'A')

위 예시에서는 graph 변수에 그래프를 인접 리스트 형태로 표현합니다. bfs 함수는 시작 노드와 그래프를 전달받아 BFS를 수행하는 함수입니다. BFS 탐색 순서는 print문으로 출력합니다.

BFS 탐색은 큐를 사용하기 때문에, collections 모듈에서 제공하는 deque 클래스를 활용하여 큐를 만들었습니다. 방문한 노드를 저장하기 위한 visited 집합을 사용하여 이미 방문한 노드를 체크합니다.

결론

BFS는 너비 우선 탐색 알고리즘으로, 그래프를 탐색하는 데에 유용합니다. 큐 자료 구조를 이용하여 간단하게 구현할 수 있으며, 최단 경로를 찾는 데에도 활용됩니다.

파이썬에서는 deque를 활용하여 큐를 구현할 수 있으며, set 자료형을 사용하여 방문한 노드를 체크할 수 있습니다. 이를 활용하여 다양한 그래프 탐색 문제를 해결할 수 있습니다.