BFS

BFS란?

BFS(Breadth-First Search, 너비 우선 탐색) 는 시작점에서 가까운 정점부터
차례로 탐색하는 방법입니다. 거리 1인 정점을 모두 본 뒤 거리 2, 그다음 거리 3...
이렇게 물결이 퍼지듯 동심원으로 넓혀 갑니다.

이 성질 덕분에 BFS는 가중치 없는 그래프의 최단 거리를 구하는 표준 도구입니다.

1. 큐가 핵심 부품

BFS는 큐(FIFO) 로 구현합니다. 큐의 "먼저 들어온 것이 먼저 나온다"는 성질이
"가까운 정점을 먼저 처리한다"를 자동으로 보장합니다.

1. 시작 정점을 큐에 넣고 방문 표시.
2. 큐에서 하나 꺼내, 이어진 정점 중 안 가본 곳을 모두 큐에 넣고 표시.
3. 큐가 빌 때까지 반복.

거리 \(d\)인 정점들이 큐에서 모두 빠진 뒤에야 거리 \(d+1\)인 정점들이 처리됩니다.

2. 최단 거리가 보장되는 이유

BFS는 정점을 거리 순서대로 방문합니다. 어떤 정점에 처음 도달했을 때의
거리가 곧 최단 거리입니다 — 더 짧은 경로가 있었다면 그 경로로 먼저 도달했을
테니까요.

그래서 BFS는 "한 출발점에서 모든 정점까지의 최단 거리(간선 수)"를 \(O(V + E)\)에
한 번에 구합니다. 단, 모든 간선의 가중치가 같을 때만 성립합니다. 가중치가
다르면 다익스트라가 필요합니다.

3. 거리 배열로 방문과 거리를 동시에

방문 여부와 거리를 따로 관리할 필요 없이, dist 배열 하나로 둘 다 처리하는 것이
깔끔합니다.

dist[시작] = 0
이웃 v가 아직 -1(미방문)이면: dist[v] = dist[현재] + 1

dist[v] != -1이면 이미 방문한 것이니, 별도 방문 배열이 필요 없습니다.

4. BFS로 푸는 대표 문제

특히 격자 미로의 최단 거리가 BFS의 간판 문제입니다.

5. 변형: 0-1 BFS, 다중 시작점

• 다중 시작점 BFS: 처음에 여러 정점을 동시에 큐에 넣으면, 가장 가까운
  시작점까지의 거리를 한 번에 구합니다(예: 여러 곳에서 동시에 번지는 불).
• 0-1 BFS: 가중치가 0과 1뿐이면, 덱을 써서 0짜리는 앞에, 1짜리는 뒤에 넣어
  다익스트라 없이 최단 거리를 구합니다.

정리

BFS는 가까운 곳부터 물결처럼 퍼지는 탐색이며, 큐로 구현합니다. 가중치 없는
그래프의 최단 거리를 \(O(V+E)\)에 구하는 것이 핵심 용도입니다. 다음 강의에서
미로 BFS를 코드로 완성합니다.

BFS를 코드로

기본 BFS와 가장 자주 나오는 격자 미로 최단 경로를 구현합니다.

1. 기본 그래프 BFS (최단 거리)

vector<int> adj[100001];
int dist[100001];

void bfs(int start) {
    fill(dist, dist + n + 1, -1);   // -1 = 미방문
    queue<int> q;
    dist[start] = 0;
    q.push(start);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : adj[u]) {
            if (dist[v] == -1) {           // 처음 도달 = 최단
                dist[v] = dist[u] + 1;
                q.push(v);                 // 넣을 때 표시 (front에서 X)
            }
        }
    }
}

from collections import deque

def bfs(start, n, adj):
    dist = [-1] * (n + 1)
    dist[start] = 0
    q = deque([start])
    while q:
        u = q.popleft()
        for v in adj[u]:
            if dist[v] == -1:
                dist[v] = dist[u] + 1
                q.append(v)
    return dist

핵심: 큐에 넣을 때 방문 표시(거리 기록)를 합니다. 꺼낼 때 표시하면 같은
정점이 큐에 여러 번 들어가 비효율적이거나 거리가 틀립니다.

2. 격자 미로 최단 경로

int dx[] = {0, 0, 1, -1}, dy[] = {1, -1, 0, 0};
int maze[1001][1001], dist[1001][1001];

int bfs(int sx, int sy, int ex, int ey) {
    queue<pair<int,int>> q;
    dist[sx][sy] = 1;            // 시작 칸도 1로 세는 문제 관례면
    q.push({sx, sy});
    while (!q.empty()) {
        auto [x, y] = q.front(); q.pop();
        for (int d = 0; d < 4; d++) {
            int nx = x + dx[d], ny = y + dy[d];
            if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;  // 밖
            if (dist[nx][ny] || maze[nx][ny] == 0) continue;        // 방문/벽
            dist[nx][ny] = dist[x][y] + 1;
            q.push({nx, ny});
        }
    }
    return dist[ex][ey];
}

def bfs(sx, sy, n, m, maze):
    dx, dy = [0, 0, 1, -1], [1, -1, 0, 0]
    dist = [[0] * m for _ in range(n)]
    dist[sx][sy] = 1
    q = deque([(sx, sy)])
    while q:
        x, y = q.popleft()
        for d in range(4):
            nx, ny = x + dx[d], y + dy[d]
            if 0 <= nx < n and 0 <= ny < m and not dist[nx][ny] and maze[nx][ny]:
                dist[nx][ny] = dist[x][y] + 1
                q.append((nx, ny))
    return dist

3. 다중 시작점 BFS

여러 출발점에서 동시에 퍼질 때는, 처음에 그 모든 점을 큐에 넣고 거리 0(또는 1)로
표시한 뒤 평소처럼 BFS합니다. 그러면 각 칸은 가장 가까운 시작점까지의 거리를
얻습니다(토마토 익히기, 불 번짐 등).

for (auto [x, y] : sources) { dist[x][y] = 0; q.push({x, y}); }
// 이후 동일한 BFS

4. 흔한 실수

• 꺼낼 때 방문 표시 — 같은 정점이 큐에 중복으로 들어가 거리가 틀리거나 느려짐.
  넣을 때 표시하세요.
• 거리 기준 혼동 — "시작 칸 포함 칸 수"인지 "이동 횟수"인지에 따라 초기값과
  답이 1 차이. 문제 정의 확인.
• 파이썬 리스트로 큐 — pop(0)는 \(O(N)\). deque.popleft() 필수.
• 격자 경계 검사 빠뜨림 — 인덱스 범위 먼저 확인.
• 가중치 다른 그래프에 BFS — 최단 거리 틀림. 다익스트라로.

5. 패턴 알아보기

• "최소 이동/최단 거리" + 모든 간선 비용 동일 → BFS.
• "미로/격자에서 최단 경로" → 격자 BFS.
• "여러 곳에서 동시에 번진다" → 다중 시작점 BFS.
• 비용이 제각각이면 BFS가 아니라 다익스트라.

실전에서 BFS 문제 알아보기

BFS 문제의 90%는 한 문장으로 요약됩니다 — "모든 이동의 비용이 같을 때
최소 횟수". 이 신호를 다양한 변장 속에서 알아보는 것이 이 단원입니다.

1. 출제 신호

• "최단 거리", "최소 횟수", "가장 빨리" + 한 번의 이동 비용이 전부 동일 —
  미로 탈출, 숨바꼭질(\(+1\), \(-1\), \(\times 2\)).
• 상태 전이 퍼즐 — 물통 붓기, 버튼 눌러 숫자 만들기. "칸"이 아니라
  상태가 정점이라는 점만 다를 뿐 같은 BFS입니다.
• 다중 시작점 — "모든 토마토에서 동시에 퍼진다", "여러 발화점". 시작점을
  전부 큐에 넣고 시작하면 끝입니다.
• 단계(레벨) 수 자체가 답 — "며칠 걸리는가".
• 이동 비용이 0과 1로 섞이거나 제각각이면 BFS가 아니라 0-1 BFS·다익스트라
  (다음 단계)임을 기억하세요.

2. 풀이 결정 절차

1. 상태를 정의합니다 — 위치만으로 충분한가, 추가 정보(벽 부순 횟수,
   열쇠 보유 등)가 필요한가? 추가 정보가 답에 영향을 주면 상태에 넣어야 합니다.
2. 이동 비용이 전부 1인지 확인합니다 — 아니라면 BFS로는 안 됩니다.
3. dist 배열을 \(-1\)로 초기화해 방문 표시를 겸하게 합니다.
4. 시작 상태(들)를 모두 큐에 넣고, 꺼낸 순서가 곧 거리 오름차순임을 이용해
   목표 도달 즉시 답을 확정합니다.

3. 자주 하는 실수

• 방문 표시를 큐에서 꺼낼 때 함. 같은 상태가 큐에 수십 번 중복으로 들어가
  메모리·시간이 폭발합니다. 넣을 때 표시가 BFS의 제1원칙입니다.

queue<int> q;
dist[start] = 0;
q.push(start);
while (!q.empty()) {
    int u = q.front(); q.pop();
    for (int v : next_states(u)) {
        if (dist[v] != -1) continue;   // 이미 큐에 들어간 상태
        dist[v] = dist[u] + 1;         // push 시점에 거리 확정 = 방문 표시
        q.push(v);
    }
}

• 상태 부족. "벽을 한 번 부술 수 있다"면 (r, c)가 아니라
  (r, c, 부쉈는지)가 상태입니다. 위치만 쓰면 오답.
• 범위 검사 순서. if (visited[nr][nc] || nr < 0) 순서로 쓰면 배열 밖을
  먼저 읽어 터집니다. 범위 검사가 항상 먼저입니다.
• 숨바꼭질류에서 상태 공간 미제한. \(\times 2\) 이동은 상한을 넘어갈 수
  있으니 배열 크기(예: \(2 \times 10^5\))로 잘라야 합니다.
• 거리 배열 없이 깊이를 세려고 함. 레벨이 필요하면 dist 배열 또는
  "현재 레벨 크기만큼 꺼내기" 패턴 중 하나를 정확히 쓰세요.

4. 연습 방법

이 페이지 오른쪽의 추천 문제는 쉬운 것부터 어려운 것 순입니다. 격자
미로 → 다중 시작점 → 상태 전이 퍼즐 순으로 상태 정의가 점점 어려워집니다.

각 문제에서 코딩 전에 "정점(상태)은 무엇이고 간선(전이)은 무엇인가"를
한 줄로 적으세요. 이 한 줄이 BFS 문제의 전부입니다. 3문제 이상 풀어
클리어하면 레이팅의 CLASS 보너스에 반영됩니다.