0-1 BFS

문제 상황

간선 가중치가 0 또는 1뿐인 그래프에서 최단 경로를 구해야 한다고 합시다.
다익스트라(\(O(E \log V)\))도 답을 주지만, 이 특수한 구조에서는 우선순위 큐가
과한 도구입니다. 덱(deque) 하나면 \(O(V+E)\) 에 끝납니다.

핵심 아이디어

BFS가 옳은 이유를 떠올려 보면 — 큐 안의 정점들이 항상 거리 순으로
정렬되어 있기 때문입니다. 가중치가 0/1이면 이 성질을 덱으로 유지할 수 있습니다.

• 가중치 0인 간선으로 이완하면, 거리가 같으므로 덱의 앞에 넣는다.
• 가중치 1인 간선으로 이완하면, 거리가 1 크므로 덱의 뒤에 넣는다.

이렇게 하면 덱 안의 거리값이 항상 단조(차이가 최대 1)로 유지되어, 앞에서
꺼내는 순서가 다익스트라의 추출 순서와 같아집니다.

왜 옳은가 (스케치)

덱 안의 원소들의 거리는 항상 \(d\) 또는 \(d+1\) 두 값뿐임을 귀납적으로 보일 수
있습니다. 앞에서 꺼낸 정점의 거리가 최소이므로, 다익스트라와 같은 논리로
확정(finalize)해도 안전합니다.

복잡도

각 정점·간선이 상수 번만 처리되므로 \(O(V+E)\). 다익스트라보다 로그 인자가
빠지고, 상수도 가볍습니다.

전형적인 등장 형태

• 미로에서 "벽 부수기 최소 횟수" — 이동은 0, 벽 부수기는 1.
• 레이저/거울 회전 문제 — 직진은 0, 방향 전환은 1.
• "최소 횟수의 특수 행동"을 묻는 격자 문제 전반.

가중치가 0과 1만 있는지 먼저 확인하세요. 0/1이 아니라 작은 정수 \(k\)까지면
다이얼(Dial's) 알고리즘이라는 일반화도 있습니다.

참조 구현 (C++)

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m;  // 정점, 간선 수
    cin >> n >> m;
    vector<vector<pair<int,int>>> adj(n + 1);  // (다음 정점, 가중치 0/1)
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }

    const int INF = 1e9;
    vector<int> dist(n + 1, INF);
    deque<int> dq;
    dist[1] = 0;
    dq.push_back(1);
    while (!dq.empty()) {
        int u = dq.front(); dq.pop_front();
        for (auto [v, w] : adj[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                if (w == 0) dq.push_front(v);  // 같은 거리 → 앞
                else        dq.push_back(v);   // +1 거리 → 뒤
            }
        }
    }
    cout << dist[n] << '\n';
}

참조 구현 (Python)

import sys
from collections import deque

input = sys.stdin.readline
n, m = map(int, input().split())
adj = [[] for _ in range(n + 1)]
for _ in range(m):
    u, v, w = map(int, input().split())
    adj[u].append((v, w))
    adj[v].append((u, w))

INF = float('inf')
dist = [INF] * (n + 1)
dist[1] = 0
dq = deque([1])
while dq:
    u = dq.popleft()
    for v, w in adj[u]:
        if dist[u] + w < dist[v]:
            dist[v] = dist[u] + w
            if w == 0:
                dq.appendleft(v)  # 가중치 0 → 앞에
            else:
                dq.append(v)      # 가중치 1 → 뒤에
ans = dist[n]
print(ans)

자주 하는 실수

• 방문 체크를 큐에 넣을 때 하는 것 — 0-1 BFS에서는 같은 정점이 여러 번
  덱에 들어갈 수 있습니다. dist 갱신 조건(dist[u]+w < dist[v])으로만
  걸러야 안전합니다. 꺼낼 때 더 좋은 기록이 이미 있으면 건너뛰는 가드를
  추가해도 됩니다.
• 격자 문제에서 상태 확장 누락 — "벽을 k번까지 부술 수 있다"류는
  (행, 열, 부순 횟수)가 상태입니다. 정점 수가 늘어난 만큼 dist 배열도 함께.
• BFS처럼 push할 때 거리를 확정하면 안 됩니다 — 0 간선 때문에 같은 거리의
  더 짧은 경로가 뒤늦게 발견될 수 있습니다.

연습 포인트

벽 부수고 이동하기류 문제에서 (이동=0/부수기=1)으로 모델링하는 연습,
그리고 같은 문제를 다익스트라로도 풀어 시간 차이를 비교해 보세요.

출제 신호

0-1 BFS는 문제가 "0-1 BFS를 쓰라"고 말해 주지 않습니다. 가중치가 0 아니면
1뿐인 그래프를 스스로 모델링해야 보입니다. 전형적인 신호는 이렇습니다.

• "벽을 최소 몇 개 부수고 도착할 수 있는가" — 빈 칸 이동은 0, 벽 부수기는 1
• "방향을 최소 몇 번 바꾸는가" — 같은 방향 직진은 0, 회전은 1
• "순간이동은 공짜, 걷기는 1초" 류의 두 종류 이동
• "규칙을 최소 몇 번 어기는가", "다리를 최소 몇 개 놓는가"

즉 "비용이 드는 행동의 횟수를 최소화"하고 나머지 이동이 공짜라면,
정점 수가 \(10^6\) 격자급이어도 \(O(V + E)\)로 풉니다. 가중치 종류가 0/1 두
가지라는 점만 확인되면 다익스트라보다 로그 인자 하나가 빠집니다.

풀이 결정 절차

1. 이동(전이)을 전부 나열하고 각각의 비용이 0 또는 1로만 떨어지는지 확인합니다.
   (0/1이 아니라 0/½ 이상 섞이면 그냥 다익스트라로 갑니다.)
2. 상태를 정의합니다 — 격자라면 (행, 열), 회전 문제라면 (행, 열, 방향)처럼
   비용 판정에 필요한 정보를 상태에 포함해야 합니다.
3. 덱(deque)을 준비합니다 — 비용 0 전이는 앞에, 비용 1 전이는 뒤에 넣습니다.
4. 복잡도 검산 — 상태 수 \(\times\) 전이 수가 \(10^7\) 안쪽인지 확인합니다.

핵심 불변식은 "덱 안의 거리값은 항상 단조(차이가 최대 1)"라는 것입니다.
그래서 다익스트라처럼 힙이 없어도 꺼내는 순서가 거리 오름차순이 됩니다.

자주 하는 실수

• 넣을 때 방문 확정 — 가중치 1짜리 BFS 습관대로 enqueue 시점에 방문
  처리하면, 나중에 비용 0 경로로 더 싸게 도달할 수 있는 상태가 막힙니다.
  거리 비교로 갱신하고, 꺼낼 때 낡은 항목을 버리는 게 안전합니다.

from collections import deque

dist = [[INF] * m for _ in range(n)]
dist[sy][sx] = 0
dq = deque([(sy, sx)])
while dq:
    y, x = dq.popleft()
    for ny, nx, w in transitions(y, x):     # w 는 0 또는 1
        if dist[y][x] + w < dist[ny][nx]:
            dist[ny][nx] = dist[y][x] + w
            if w == 0:
                dq.appendleft((ny, nx))     # 0 은 앞으로
            else:
                dq.append((ny, nx))         # 1 은 뒤로

• 0 전이를 뒤에 넣음 — appendleft/push_front를 빼먹으면 그냥 틀린
  BFS가 됩니다. 0과 1의 행선지(앞/뒤)를 제출 전에 꼭 확인하세요.
• 상태 부족 — "방향 전환 최소화"에서 (행, 열)만 들고 가면 같은 칸을
  다른 방향으로 지나는 경우를 구분하지 못해 오답입니다. (행, 열, 방향)으로 확장.
• 다익스트라로 풀어도 되는데 시간이 빠듯한 경우 — \(10^6\) 상태 \(\times\)
  \(\log\)가 아슬아슬하면 0-1 BFS로 바꾸는 것 자체가 정해인 문제도 있습니다.

연습 방법

사이드바 연습 목록에서 "벽 부수기" 류의 격자 문제부터 시작해, 상태에
방향이 들어가는 회전 문제로 올라가세요. 문제를 읽을 때 "공짜 행동 / 1짜리
행동"을 표로 적어 보고, 그래프 모델링이 끝난 뒤에야 코드를 시작하는 습관이
중요합니다. 같은 문제를 다익스트라로도 한 번 풀어 두 구현의 차이(힙 vs 덱)를
비교해 보면 이해가 굳어집니다. 태그된 문제 3문제 이상 해결 시 마스터
처리되어 레이팅 CLASS 보너스에 반영됩니다.