BFS 알고리즘 (너비 우선 탐색, Breadth-First Search)

너비 우선 탐색(BFS, Breadth-First Search) 알고리즘은 그래프나 트리의 노드를 탐색하는 방법으로, 특정 시작 노드에서부터 인접한 모든 노드를 탐색한 다음, 그 다음 수준의 노드로 이동하여 다시 탐색하는 방식입니다.

동작 원리

1. 시작 노드 선택: 탐색을 시작할 노드를 선택합니다.
2. 큐 사용: BFS는 큐(Queue) 자료구조를 사용하여 탐색할 노드를 관리합니다. 먼저 들어온 노드가 먼저 나가는 FIFO(First In, First Out) 방식입니다.
3. 탐색: 시작 노드를 큐에 추가하고, 큐가 빌 때까지 다음을 반복합니다:
   • 큐에서 노드를 꺼내어 방문합니다.
   • 방문한 노드의 인접 노드를 큐에 추가하고, 이때 방문하지 않은 노드만 추가합니다.
4. 종료 조건: 모든 노드를 탐색할 때까지 이 과정을 반복합니다.

---

BFS의 구현

BFS는 큐를 사용하여 구현할 수 있으며, Python의 collections 모듈에 있는 deque를 사용하는 것이 효율적입니다.

from collections import deque

def bfs(graph, start):
    visited = set()  # 방문한 노드를 기록할 집합
    queue = deque([start])  # 시작 노드를 큐에 추가

    while queue:
        node = queue.popleft()  # 큐의 맨 앞 노드 꺼내기
        if node not in visited:
            print(node)  # 노드 방문
            visited.add(node)  # 방문한 노드 기록
            # 인접 노드를 큐에 추가
            for neighbor in graph[node]:
                if neighbor not in visited:
                    queue.append(neighbor)  # 방문하지 않은 노드만 추가

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

# BFS 호출
bfs(graph, 'A')

 

---

BFS의 특징

• 장점:
  • 최단 경로 문제를 해결할 때 유용합니다. BFS는 가장 먼저 도달한 경로가 최단 경로임을 보장합니다.
  • 특정 노드까지의 거리를 계산할 때 유용합니다.
• 단점:
  • 메모리 사용량이 많을 수 있습니다. 특히, 노드의 수가 많거나 깊이가 깊은 그래프의 경우, 모든 노드를 큐에 저장해야 하므로 메모리를 많이 사용합니다.
  • 트리의 깊이가 깊거나 넓은 경우(너비가 넓은 경우) 탐색 시간이 느려질 수 있습니다.