BFS(너비 우선 탐색) 알고리즘: 동작 원리와 Python 코드 구현

너비 우선 탐색 (Breadth-First Search)란?

Breadth-First Search (BFS)는 현재 깊이 수준에 있는 모든 노드를 탐색한 후 다음 깊이 수준의 노드를 탐색하는 그래프 순회 알고리즘입니다. 가중치가 없는 그래프에서 최단 경로 문제를 해결하거나, 트리 탐색 및 연결 요소 분석 등에 널리 사용됩니다.

BFS 알고리즘 설명

BFS는 큐(queue) 자료구조를 사용하여 다음에 탐색할 노드를 추적합니다. 핵심 아이디어는 다음과 같습니다:

• 시작 노드를 방문하고 큐에 추가합니다.
• 큐가 비어있지 않은 동안:
  • 큐의 앞쪽에서 노드를 꺼냅니다.
  • 노드를 처리합니다 (예: 출력, 기록).
  • 방문하지 않은 모든 이웃 노드를 큐에 추가합니다.

알고리즘 단계 (이진 트리)

1. 루트 노드를 시작으로 큐에 추가합니다.
2. 큐가 비어있지 않은 동안:
   • 큐에서 노드를 꺼냅니다.
   • 현재 노드를 처리합니다.
   • 왼쪽 자식이 존재하면 큐에 추가합니다.
   • 오른쪽 자식이 존재하면 큐에 추가합니다.

알고리즘 단계 (일반 그래프)

1. 주어진 노드를 시작으로 큐에 추가합니다.
2. 방문 집합(visited set)을 사용하여 방문 여부를 추적합니다.
3. 큐가 비어있지 않은 동안:
   • 큐에서 노드를 꺼냅니다.
   • 노드를 처리합니다.
   • 각 이웃 노드에 대해:
     • 방문하지 않았다면 방문 표시하고 큐에 추가합니다.

Python 예제 코드

1. 이진 트리에서 BFS

from collections import deque

class TreeNode:
    def __init__(self, value):
        self.val = value
        self.left = None
        self.right = None

def bfs_binary_tree(root):
    if not root:
        return

    queue = deque([root])

    while queue:
        node = queue.popleft()
        print(node.val)

        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)

# 예제 실행
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)

bfs_binary_tree(root)

실행결과:

1
2
3
4
5

 

2. 일반 그래프에서 BFS

from collections import deque

def bfs_graph(graph, start):
    visited = set()
    queue = deque([start])
    visited.add(start)

    while queue:
        node = queue.popleft()
        print(node)

        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

# 예제 실행
graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['F'],
    'F': []
}

bfs_graph(graph, 'A')

실행결과:

A
B
C
D
E
F

시간 및 공간 복잡도 분석

이진 트리

• 시간 복잡도: $O(n)$ (노드 수 n 만큼 방문)
• 공간 복잡도: $O(w)$ (트리의 최대 너비 w)

일반 그래프

• 시간 복잡도: $O(V + E)$ (정점 수 V, 간선 수 E)
• 공간 복잡도: $O(V)$ (방문 집합과 큐 저장)

결론

BFS는 그래프나 트리를 직관적이고 효율적으로 순회하는 방법 중 하나입니다. 가중치가 없는 그래프에서는 가장 짧은 경로를 보장하며, 복잡한 시스템에서 강력한 알고리즘을 설계할 때 반드시 이해해야 할 핵심 기법입니다.

참고 문헌

• Wikipedia - Breadth-First Search
• GeeksforGeeks - BFS for a Graph