0-1 BFS

정의

0-1 BFS 는 간선 가중치가 0 또는 1만 존재하는 그래프에서 최단 경로를 O(V + E) 에 구하는 알고리즘. deque 를 사용해 가중치 0 간선은 앞에, 가중치 1 간선은 뒤에 추가하여 BFS 의 단조성을 유지한다.

Dial’s algorithm (1969) 의 특수 케이스로, 다익스트라의 우선순위 큐 대신 deque 로 충분.

문제 상황과 동기

가중치 그래프의 최단 경로 알고리즘:

• BFS: 간선 가중치가 모두 같을 때 (unweighted). O(V + E).
• Dijkstra: 간선 가중치 ≥ 0. O((V + E) log V) (우선순위 큐 사용).
• 0-1 BFS: 간선 가중치가 0 또는 1만. O(V + E).

예: 격자에서 “벽을 최대 1개 부수고 이동” 류 문제. 일반 이동 (비용 0), 벽 부수기 (비용 1). Dijkstra 는 느리고 BFS 는 불가능. 0-1 BFS 가 딱 맞는다.

핵심 통찰: 가중치가 0, 1 두 종류만 있으면 거리 증가 순서가 최대 2단계 (d, d+1) 만 큐에 공존. deque 앞쪽 = d, 뒷쪽 = d+1. BFS 의 단조성 유지.

시각화

핵심 아이디어

invariant: deque 내 거리가 비감소 (non-decreasing). 앞쪽이 항상 최소.

dist[v] = ∞ for all v
dist[s] = 0
deque dq = {s}

while dq not empty:
    u = dq.pop_front()
    for (v, w) in adj[u]:   # w ∈ {0, 1}
        if dist[u] + w < dist[v]:
            dist[v] = dist[u] + w
            if w == 0:
                dq.push_front(v)
            else:
                dq.push_back(v)

왜 작동하는가:

• 가중치 0: 거리 그대로. 앞에 추가 → 먼저 처리.
• 가중치 1: 거리 +1. 뒤에 추가 → 나중 처리.
• deque 내부 거리가 [d, d, …, d+1, d+1, …] 형태로 정렬 유지.
• BFS 와 동일하게 각 노드 최대 1회 처리 (최초 pop 시 최단).

Dijkstra 와의 차이:

가중치 범위가 {0, 1} 로 제한되면 deque 의 앞/뒤 삽입 O(1) 이 heap 의 O(log V) 보다 빠르다.

알고리즘

0-1-BFS(G, s):
    dist[v] ← ∞ for all v ∈ V
    dist[s] ← 0
    dq ← deque()
    dq.push_back(s)
    
    while dq not empty:
        u ← dq.pop_front()
        
        for each edge (u, v, w) in adj[u]:  # w ∈ {0, 1}
            if dist[u] + w < dist[v]:
                dist[v] ← dist[u] + w
                
                if w == 0:
                    dq.push_front(v)
                else:
                    dq.push_back(v)
    
    return dist

구현

// 0-1 BFS, deque push_front (w=0) / push_back (w=1)
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
​
int main() {
  int n, m, s, t;
  cin >> n >> m >> s >> t;  // n nodes, m edges, source s, target t
  
  vector<vector<pair<int, int>>> adj(n + 1);
  for (int i = 0; i < m; i++) {
      int u, v, w;
      cin >> u >> v >> w;  // w ∈ {0, 1}
      adj[u].push_back({v, w});
      adj[v].push_back({u, w});  // undirected
  }
  
  vector<int> dist(n + 1, INF);
  deque<int> dq;
  dist[s] = 0;
  dq.push_back(s);
  
  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);
          }
      }
  }
  
  cout << (dist[t] == INF ? -1 : dist[t]) << "\n";
}

# 0-1 BFS, collections.deque appendleft/append
from collections import deque
import sys
input = sys.stdin.readline
INF = 10**9
​
n, m, s, t = map(int, input().split())
adj = [[] for _ in range(n + 1)]
​
for _ in range(m):
  u, v, w = map(int, input().split())  # w ∈ {0, 1}
  adj[u].append((v, w))
  adj[v].append((u, w))
​
dist = [INF] * (n + 1)
dist[s] = 0
dq = deque([s])
​
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)
          else:
              dq.append(v)
​
print(-1 if dist[t] == INF else dist[t])

// 0-1 BFS, ArrayDeque addFirst/addLast
import java.util.*;
import java.io.*;
​
public class Main {
  static class Edge {
      int to, w;
      Edge(int to, int w) { this.to = to; this.w = w; }
  }
  
  public static void main(String[] args) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st = new StringTokenizer(br.readLine());
      int n = Integer.parseInt(st.nextToken());
      int m = Integer.parseInt(st.nextToken());
      int s = Integer.parseInt(st.nextToken());
      int t = Integer.parseInt(st.nextToken());
      
      List<Edge>[] adj = new ArrayList[n + 1];
      for (int i = 0; i <= n; i++) adj[i] = new ArrayList<>();
      
      for (int i = 0; i < m; i++) {
          st = new StringTokenizer(br.readLine());
          int u = Integer.parseInt(st.nextToken());
          int v = Integer.parseInt(st.nextToken());
          int w = Integer.parseInt(st.nextToken());  // w ∈ {0, 1}
          adj[u].add(new Edge(v, w));
          adj[v].add(new Edge(u, w));
      }
      
      int[] dist = new int[n + 1];
      Arrays.fill(dist, Integer.MAX_VALUE);
      dist[s] = 0;
      
      Deque<Integer> dq = new ArrayDeque<>();
      dq.addLast(s);
      
      while (!dq.isEmpty()) {
          int u = dq.pollFirst();
          
          for (Edge e : adj[u]) {
              if (dist[u] + e.w < dist[e.to]) {
                  dist[e.to] = dist[u] + e.w;
                  if (e.w == 0) dq.addFirst(e.to);
                  else dq.addLast(e.to);
              }
          }
      }
      
      System.out.println(dist[t] == Integer.MAX_VALUE ? -1 : dist[t]);
  }
}

5 7 1 5
1 2 0
1 3 1
2 3 0
2 4 1
3 4 0
3 5 1
4 5 0

2

3 1 1 3
1 2 1

-1

복잡도

각 노드는 deque 에 최대 2회 삽입 (가중치 0 으로 한 번, 1 로 한 번). 따라서 여전히 O(V + E).

변형 / 활용

1. 0-K BFS

간선 가중치가 0..K (K 작음) 이면 deque 대신 K+1 개 bucket 사용. O(V + E) 유지. K=1 이 0-1 BFS.

2. 격자 그래프 + 벽 부수기

격자에서 일반 이동 (비용 0), 벽 부수기 (비용 1). 0-1 BFS 로 “벽 최소 부숨” 경로.

// 격자 0-1 BFS, (x, y, 벽 부순 횟수) 상태
dist[x][y] = INF;
deque<pair<int,int>> dq;
dq.push_back({sx, sy});
dist[sx][sy] = 0;

while (!dq.empty()) {
    auto [x, y] = dq.front(); dq.pop_front();
    for (auto [dx, dy] : dirs) {
        int nx = x + dx, ny = y + dy;
        if (!valid(nx, ny)) continue;
        int w = (grid[nx][ny] == '#' ? 1 : 0);
        if (dist[x][y] + w < dist[nx][ny]) {
            dist[nx][ny] = dist[x][y] + w;
            if (w == 0) dq.push_front({nx, ny});
            else dq.push_back({nx, ny});
        }
    }
}

3. 최대 K 번 벽 부수기

상태를 (x, y, 부순 횟수 k) 로 확장. 3차원 배열 dist[x][y][k]. 0-1 BFS 그대로.

함정

1. deque 방향 착각

w == 0 일 때 push_front, w == 1 일 때 push_back. 반대로 하면 단조성 깨져 틀림.

2. 중복 방문 처리

deque 에 같은 노드가 여러 번 들어갈 수 있다. dist[v] 갱신 후 push. pop 시 이미 최소 거리면 skip.

while (!dq.empty()) {
    int u = dq.front(); dq.pop_front();
    // 이미 처리된 노드 (거리 갱신 없음)
    // if (processed[u]) continue;  // 선택적
    for (auto [v, w] : adj[u]) { ... }
}

3. 가중치 범위 확인

간선 가중치가 {0, 1} 이 아니면 0-1 BFS 불가능. 2 이상 있으면 Dijkstra.

4. 음수 가중치

0-1 BFS 는 음수 가중치 불가. 가중치 0, 1 ≥ 0 이므로 OK. 음수 있으면 Bellman-Ford.

BOJ 연습 문제

참고

• 너비 우선 탐색
• 다익스트라 알고리즘
• 격자 그래프