[Graph Algorithms] BFS (Breadth-First Search)

1. BFS란?

• Breadth-First Search (너비 우선 탐색): 시작점에서 가까운 정점부터 차례로 탐색하는 알고리즘
• Level (깊이): BFS에서는 “탐색 단계(거리)”와 동일
• Branch (가지): 한 정점에서 연결된 이웃 노드들

DFS는 깊이(Level)를 따라가며 탐색하지만, BFS는 Level 단위로 탐색
즉, “가장 가까운 노드 → 그다음 가까운 노드” 순서로 방문

---

2. BFS의 특징

• 큐(Queue)를 사용하여 구현. (FIFO: 먼저 들어온 것이 먼저 나감)
• 최단 경로 탐색에 자주 사용됨. (예: 미로, 토마토, 뱀과 사다리 게임)
• 방문 순서가 “Level Order Traversal” 형태

---

3. BFS 수도코드

procedure BFS(start):
    create queue Q
    mark start visited
    enqueue (start, level=0) to Q

    while Q not empty:
        node, level ← dequeue
        for each neighbor of node:
            if not visited[neighbor]:
                mark neighbor visited
                enqueue (neighbor, level+1)

---

4. BFS 파이썬 구현 (주석 포함)

예시 그래프 (인접 리스트)

1 - 2 - 5
|   |
3   4

코드

from collections import deque

# 그래프 (인접 리스트)
graph = {
    1: [2, 3],
    2: [1, 4, 5],
    3: [1],
    4: [2],
    5: [2]
}

def bfs(start):
    visited = set()           # 방문한 노드 기록
    q = deque([(start, 0)])   # (노드, level)
    visited.add(start)

    while q:
        node, level = q.popleft()
        print(f"노드 {node} 방문 (level={level})")

        # branch: 현재 노드의 모든 이웃 탐색
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                q.append((neighbor, level+1))

bfs(1)

실행 흐름

노드 1 방문 (level=0)
노드 2 방문 (level=1)
노드 3 방문 (level=1)
노드 4 방문 (level=2)
노드 5 방문 (level=2)

Level: 시작점 1은 level=0, 이웃 노드들은 level=1, 그 다음은 level=2
Branch: 1번에서 2와 3으로 동시에 확장

---

5. 흔히 헷갈리는 지점

❌ 오개념 1: BFS도 재귀로 구현할 수 있지 않나?

• BFS는 큐(FIFO) 구조로 “순차적으로” 탐색해야 하므로, 보통 반복문 + 큐로 구현
• DFS는 스택/재귀와 찰떡궁합이지만, BFS를 재귀로 구현하면 오히려 복잡

❌ 오개념 2: DFS와 BFS의 차이가 헷갈린다

• DFS: “깊이 우선” (한 갈래를 끝까지 파고듦 → backtracking)
• BFS: “너비 우선” (가까운 노드를 먼저 방문 → 점차 넓혀감)
• BFS는 최단 거리 문제에, DFS는 경로 탐색·백트래킹 문제에 자주 쓰임

❌ 오개념 3: 방문 체크 시점

• BFS에서는 큐에 넣을 때(Enqueue 시점) 방문 표시를 하는 게 안전
• 그렇지 않으면 같은 노드가 큐에 여러 번 들어갈 수 있음

---

6. BFS 활용 예시 — 최단 거리 구하기

코드

from collections import deque

def shortest_path(start, target, graph):
    visited = {start: 0}
    q = deque([start])

    while q:
        node = q.popleft()
        if node == target:
            return visited[node]

        for neighbor in graph[node]:
            if neighbor not in visited:
                visited[neighbor] = visited[node] + 1  # 거리 갱신
                q.append(neighbor)

    return -1  # target에 도달 불가

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

print(shortest_path(1, 5, graph))  # 출력: 2

BFS의 level 정보 = 최단 거리임을 확인할 수 있음

---

추천 백준 문제 (BFS 연습)

1. 백준 2178번 미로 탐색
   → BFS로 최단 경로를 구하는 대표 문제

2. 백준 7562번 나이트의 이동
   → 체스판에서 나이트 이동 최단 횟수

3. 백준 1697번 숨바꼭질
   → 1차원에서 BFS를 적용하는 기본기 문제