너비 우선 탐색(BFS) 알고리즘

개요

너비 우선 탐색(Breadth-First Search, BFS)은 그래프나 트리에서 루트 노드(혹은 다른 임의의 노드)에서 시작하여 인접한 노드를 먼저 탐색하는 방법입니다. 즉, 깊게(deep) 탐색하기 전에 넓게(wide) 탐색하는 방식입니다.

동작 원리

1. 시작 노드를 방문하고, 해당 노드를 큐(Queue)에 삽입합니다.
2. 큐에서 노드를 꺼내어(dequeue) 해당 노드에 인접한 방문하지 않은 모든 노드를 큐에 삽입(enqueue)하고, 방문 처리를 합니다.
3. 2번 과정을 큐가 빌(empty) 때까지 반복합니다.

이러한 과정을 통해 BFS는 시작 노드로부터 가까운 노드부터 차례대로 탐색하게 됩니다.

특징

• 최단 경로 보장: BFS는 가중치가 없는 그래프에서 두 노드 사이의 최단 경로를 보장합니다.

• 구현의 복잡성: BFS는 깊이 우선 탐색(DFS)보다 구현이 다소 복잡합니다.

• 메모리 사용량: BFS는 큐(Queue)를 사용하므로, 탐색 과정에서 많은 메모리를 사용할 수 있습니다.

파이썬 구현 예시

from collections import deque

def bfs(graph, start_node):
    visited = set()  # 방문한 노드를 저장할 집합
    queue = deque([start_node])  # 시작 노드를 큐에 삽입

    while queue:
        node = queue.popleft()  # 큐에서 노드를 꺼냄
        if node not in visited:
            visited.add(node)  # 노드를 방문 처리
            print(node, end=' ')  # 방문한 노드 출력
            # 인접 노드 중 방문하지 않은 노드를 큐에 삽입
            queue.extend(neighbor for neighbor in graph[node] if neighbor not in visited)

# 그래프를 인접 리스트로 표현
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

# 함수 호출
bfs(graph, 'A')

출력 결과:

A B C D E F

위 예시에서 그래프는 인접 리스트로 표현되었으며, BFS를 통해 'A' 노드부터 탐색을 시작하여 인접한 노드를 차례로 방문합니다.

시간 및 공간 복잡도

• 시간 복잡도: BFS는 그래프의 모든 노드와 모든 간선을 한 번씩 탐색하므로, O(V + E)의 시간 복잡도를 가집니다. 여기서 V는 노드의 수, E는 간선의 수를 의미합니다.

• 공간 복잡도: BFS는 큐에 최대 O(V)의 노드를 저장하므로, 공간 복잡도는 O(V)입니다.

활용 예시

• 최단 경로 탐색: BFS는 가중치가 없는 그래프에서 두 노드 사이의 최단 경로를 찾는 데 사용됩니다.

• 그래프의 연결성 확인: BFS를 통해 그래프의 연결 요소를 확인하거나, 특정 노드가 다른 노드와 연결되어 있는지 확인할 수 있습니다.

• 이진 트리의 레벨 순회: 이진 트리에서 BFS를 사용하여 각 레벨의 노드를 순서대로 방문할 수 있습니다.

BFS는 이러한 특성과 활용도를 지니고 있어, 그래프 탐색 및 최단 경로 문제 등 다양한 분야에서 널리 사용됩니다.