🧭 BFS (Breadth-First Search) 완전 정리

---

✅ BFS란?

BFS(Breadth-First Search, 너비 우선 탐색)는 시작 정점에서 인접한 노드를 먼저 탐색하고,
그 다음 레벨의 노드를 탐색해 나가는 방식의 알고리즘이다.
탐색의 흐름이 큐(Queue) 구조를 따른다.

---

📌 BFS in Tree - 트리에서의 BFS (Level Order Traversal)

✅ 핵심 개념

• 루트에서부터 한 레벨씩 순차적으로 탐색
• 트리는 사이클이 없기 때문에 방문 배열이 필요 없다
• 일반적으로 레벨 순회(Level-order Traversal)라고 부른다

✅ 예시 트리

        A
       / \
      B   C
     / \
    D   E

레벨 순회 결과: A → B → C → D → E

✅ 구현 (파이썬)

from collections import deque

def level_order(root):
    if not root:
        return
    queue = deque([root])

    while queue:
        node = queue.popleft()
        print(node.key, end=' ')
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)

# 트리 생성
class Node:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None

root = Node('A')
root.left = Node('B')
root.right = Node('C')
root.left.left = Node('D')
root.left.right = Node('E')

level_order(root)  # 출력: A B C D E

---

📌 BFS in Graph - 그래프에서의 BFS

✅ 핵심 개념

• 가장 가까운 정점부터 순차적으로 방문
• 모든 노드를 최단 거리 순으로 방문하게 된다
• 방문 체크 배열 필수 (그래프는 사이클/분기 존재 가능)

✅ BFS 동작 방식

1. 시작 노드를 큐에 넣고 방문 처리
2. 큐에서 노드를 꺼내고, 인접 노드들을 큐에 넣는다
3. 아직 방문하지 않은 인접 노드만 넣는다

→ 큐를 중심으로 한 단계씩 확장해나가는 탐색

✅ 예제 (파이썬)

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:
                visited.add(neighbor)
                queue.append(neighbor)

graph = {
    0: [1, 2],
    1: [0, 3, 4],
    2: [0],
    3: [1],
    4: [1]
}

bfs(graph, 0)  # 출력: 0 1 2 3 4

---

🔄 트리 BFS vs 그래프 BFS

항목	그래프 BFS	트리 BFS (레벨 순회)
방문 배열	필요 ✅	필요 ❌ (사이클 없음)
탐색 방식	연결된 모든 노드 큐 삽입	왼쪽 → 오른쪽 자식 순서로 큐 삽입
응용	최단 거리, 연결 요소, 경로	레벨 기반 처리, 트리 시각화
깊이 우선성	없음	레벨 우선이므로 루트와 가까운 노드부터 탐색
시간 복잡도	O(V + E)	O(N)

---

✅ BFS 대표 활용

• 최단 거리 탐색 (가중치 없음)
• 미로 탐색 / 퍼즐 풀이
• 연결 요소 개수 세기
• 그래프 레벨 분리 탐색
• 위상 정렬, 네트워크 흐름 등 고급 알고리즘의 기반

---

🎯 마무리 요약

• BFS는 너비 우선 탐색으로, 가까운 노드부터 차례로 방문 하는 탐색 방식이다.
• 그래프에서는 방문 배열이 필요 하며, 최단 거리 탐색 에 많이 쓰인다.
• 트리에서는 레벨 순회 라고 부르며, 사이클이 없기 때문에 구조가 단순하다.
• DFS와 함께 그래프/트리 알고리즘의 핵심 탐색 방식이므로 반드시 익혀야 한다.