0-1 BFS: 무료 이동과 유료 이동

BFS의 모든 이동 비용이 1이라는 조건을 바꾸어 보겠습니다. 무료 이동이 섞이면 먼저 발견한 경로가 답이 아닐 수 있습니다. Dijkstra로도 풀 수 있지만, 비용이 0과 1뿐이면 deque의 양 끝만으로 거리 순서를 유지할 수 있습니다.

0-1 BFS는 간선 비용이 0 또는 1인 그래프에서 최단거리를 구하는 알고리즘입니다. 일반 BFS처럼 큐를 쓰지만, 비용이 0인 이동은 앞에 넣고 비용이 1인 이동은 뒤에 넣기 위해 deque를 사용합니다.

간선 비용이 0 또는 1일 때

일반 BFS는 모든 간선 비용이 1일 때만 최단거리를 보장합니다. 비용이 0인 간선이 섞이면, 한 번 이동했는데 거리 증가가 없을 수 있습니다.

u --0--> v  거리 증가 없음
u --1--> w  거리 1 증가

이때 Dijkstra를 써도 됩니다. 하지만 비용이 0과 1뿐이라면 우선순위 큐 대신 deque만으로 더 간단하게 처리할 수 있습니다.

deque를 쓰는 이유

그림 크게 보기

괄호는 정점의 거리 후보입니다. 두 이웃의 기존 거리가 더 컸다고 가정하면 비용 0의 v는 현재 거리 층에, 비용 1의 w는 다음 거리 층에 들어갑니다.

현재 정점 u에서 이웃 v로 가는 비용이 0이면 dist[v]는 dist[u]와 같습니다. 이 정점은 지금 처리 중인 거리 그룹과 같은 우선순위이므로 deque 앞쪽에 넣습니다.

비용이 1이면 다음 거리 그룹이므로 뒤쪽에 넣습니다.

cost 0: push_front
cost 1: push_back

이렇게 하면 deque의 앞쪽에는 항상 현재까지 가장 작은 거리 후보가 옵니다.

먼저 발견한 비용 1이 나중에 0이 될 때

그림 크게 보기 · deque와 거리 갱신 실험

간선이 0→1(1), 0→2(0), 2→1(0) 순서로 있다면, 0을 꺼낸 뒤 deque는 [2,1]입니다. 1은 먼저 발견되었지만 2를 앞에 넣어 먼저 처리합니다. 2에서 1로 가면 dist[1]이 1에서 0으로 줄고, 1을 다시 앞에 넣습니다.

일반 BFS처럼 처음 넣은 순간 이후 갱신을 금지하면 이 예제에서 1을 답으로 남깁니다. 0-1 BFS는 아직 더 짧은 후보를 허용하고, 새 비용이 엄격하게 작을 때만 넣습니다. 이 조건 때문에 비용 0인 사이클에서도 같은 거리로 무한히 재삽입하지 않습니다.

실험은 아래 로컬 연습과 같은 5개 정점을 사용합니다. deque 칩의 넣을 때 거리는 이력 설명용입니다. 원본 코드는 정점 번호만 저장하며, 꺼낸 뒤에는 **최신 dist[u]**를 읽습니다. 이미 개선된 정점의 옛 항목을 다시 꺼내도 이웃을 검사하되, 더 짧아지지 않으면 넣지 않습니다. Dijkstra 실습의 ‘낡은 항목 즉시 건너뛰기’와 처리 방식이 다릅니다.

기본 구현

코드 환경: 일반 C++17 학습용. 헤더·STL을 허용하는 로컬 예제입니다. h-contest 제출에 옮길 때는 공통 코드와 문제의 공개 API에 맞춰 필요한 부분을 바꿉니다.

struct Edge {
    int to;
    int cost; // 0 or 1
};

vector<int> zeroOneBfs(const vector<vector<Edge>>& graph, int start) {
    const int INF = 1e9;
    int n = (int)graph.size();
    vector<int> dist(n, INF);
    deque<int> dq;

    dist[start] = 0;
    dq.push_back(start);

    while (!dq.empty()) {
        int u = dq.front();
        dq.pop_front();

        for (const Edge& e : graph[u]) {
            int nd = dist[u] + e.cost;
            if (nd >= dist[e.to]) continue;
            dist[e.to] = nd;
            if (e.cost == 0) dq.push_front(e.to);
            else dq.push_back(e.to);
        }
    }

    return dist;
}

일반 BFS처럼 처음 발견한 순간 방문을 확정하지 않습니다. 더 짧은 0비용 경로가 나중에 발견될 수 있어 같은 정점이 deque에 여러 번 들어갈 수 있습니다. deque에 넣은 거리 후보는 두 인접 거리 층으로 정렬됩니다. 한 정점은 같은 층의 0비용 경로로 한 번 더 개선될 수 있지만 반복 개선이 누적되지는 않아 전체 복잡도는 O(V + E)입니다.

격자 상태 그래프 예시

방향을 바꾸는 비용이 1이고, 같은 방향으로 가는 비용이 0인 격자 문제를 생각해 봅시다. 상태는 (r, c, dir)이고, 이동 비용은 방향이 바뀌는지에 따라 정합니다.

이런 문제는 단순 칸 방문 배열로는 부족합니다. 같은 칸이라도 어떤 방향으로 들어왔는지에 따라 다음 비용이 달라지므로 방향까지 상태에 포함해야 합니다.

어떤 큐를 선택할까

간선 비용	사용할 도구	갱신 기준
모두 1	BFS의 일반 큐	처음 발견한 거리가 최단거리
0 또는 1	0-1 BFS의 deque	더 짧으면 앞 또는 뒤에 재삽입
일반적인 비음수	Dijkstra의 최소 힙	더 짧은 후보를 넣고 오래된 후보는 제외

비용 2인 간선을 ‘양수이므로 뒤에 넣기’로 처리하면 두 거리 층이라는 근거가 깨집니다. 아래 실행 파일은 비용 0과 1만 받습니다. 0-1 BFS를 간선 수가 가장 적은 경로를 구하는 BFS로 해석해서도 안 됩니다. 무료 간선을 더 많이 거치는 길이 더 쌀 수 있습니다.

시간 복잡도

작업	시간
초기화	`O(V)`
간선 relax 전체	`O(E)`
deque 삽입/삭제	`O(V + E)`
전체	`O(V + E)`
메모리	`O(V + E)`

로컬 연습: 무료 간선과 유료 간선

방향 그래프에서 시작점부터 모든 정점까지의 최소 비용을 구하세요. 간선 비용은 0 또는 1입니다.

입력: N M S 뒤 M줄의 u v w. 1 <= N <= 200000, 0 <= M <= 400000, 정점은 0-based입니다. 중복 간선과 self-loop를 허용합니다.

출력: 정점 번호순 최소 비용을 한 줄에 출력하고 도달 불가 정점은 -1로 표시합니다.

예시

0 0 0 1 -1

확인 방법: 0→2→1은 비용 0입니다. 작은 입력은 Dijkstra와 비교합니다. 비용 0의 cycle, 더 비싼 경로로 먼저 발견되는 정점, 고립 정점을 검사합니다. 최초 발견만으로 거리를 확정하지 말고 더 짧아질 때 갱신합니다.

완성 파일로 실행하고 확인하기

C++17 전체 예제 내려받기

c++ -std=c++17 -O2 zero-one-bfs.cpp -o lesson
./lesson < input.txt

본문의 zeroOneBfs 함수와 헤더, 입력 처리, main을 모두 포함합니다. 위의 N M S 연습 입력을 넣으면 0 0 0 1 -1을 출력합니다. 방향 간선이며, 무방향 문제라면 간선을 양쪽에 넣습니다.

1 ≤ N ≤ 200000, 0 ≤ M ≤ 400000, 정점은 0..N-1, 비용은 0 또는 1입니다. 잘못된 정점 번호와 비용 2 같은 입력은 거부합니다. 내부 미도달 값은 INF지만 출력에서는 -1로 바꿉니다. 정점 하나에 간선이 없고 시작점이 0이면 출력은 0입니다.

원본처럼 deque에는 정점 번호만 저장합니다. 같은 정점이 다시 들어갈 수 있으므로 ‘visited 배열로 한 번만 넣기’를 추가하지 마세요. 완성된 거리는 작은 그래프의 Floyd-Warshall 또는 Dijkstra와 비교할 수 있습니다. 무료 사이클, 평행 간선, self-loop, 도달 불가를 포함해 검사합니다.