BFS (Breadth-First Search)

BFS란?

• 너비 우선 탐색: 가까운 정점부터 넓게 탐색
• Queue(큐) 자료구조를 사용해 구현
• 시작점에서 인접한 정점을 먼저 탐색 후, 더 깊은 곳으로 진행

---

사용 목적

목적	설명
최단 거리 탐색	가중치 없는 그래프에서 가장 짧은 거리 보장
단계별 탐색	거리 개념이 있는 문제
연결 요소 확인	연결된 구성 요소를 모두 찾을 때
실시간 확산 구조	전파, 감염, 퍼짐 등 문제 유형에 적합

---

동작 순서

1. 시작 노드를 큐에 넣고 방문 처리
2. 큐에서 노드를 꺼냄
3. 인접 노드를 모두 큐에 추가
4. 큐가 빌 때까지 반복

---

구현 예시 (Python)

from collections import deque

def bfs(graph, start, visited):
    queue = deque([start])
    visited[start] = True

    while queue:
        v = queue.popleft()
        print(v, end=' ')
        for neighbor in graph[v]:
            if not visited[neighbor]:
                queue.append(neighbor)
                visited[neighbor] = True

# 호출 예시
graph = [
    [],         # 0번 노드 미사용
    [2, 3],     # 1 → 2, 3
    [1, 4],
    [1, 4],
    [2, 3]
]
visited = [False] * 5
bfs(graph, 1, visited)  # 출력: 1 2 3 4

---

시간 복잡도

• O(N + M)
  (N: 노드 수, M: 간선 수)

---

실전 예시 문제

유형	설명
미로 탐색	최단 거리 찾기
전염 시뮬레이션	바이러스 전파, 물 확산 등
거리 계산	특정 노드에서 모든 노드까지 거리
연결 요소	연결된 덩어리 개수 파악

---

핵심 요약

• BFS는 가까운 노드부터 탐색
• Queue 사용 + 방문 체크 필수
• 가중치 없는 최단 거리 문제에서 가장 많이 사용됨
• Python은 deque, C는 배열 기반 큐 직접 구현