0-1 BFS: 무료 이동과 유료 이동
이 글의 목차
← 기록 / 강의 / 그래프 탐색

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

비용 0과 1인 간선을 deque로 처리하고, 처음 발견한 거리가 바뀌는 과정을 봅니다.

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를 쓰는 이유

거리4인 u에서 비용0의 v는 deque 앞에, 비용1의 w는 뒤에 넣어 거리4와5의 순서를 유지합니다.

그림 크게 보기

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

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

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

cost 0: push_front
cost 1: push_back

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

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

0에서 1로 직접 가는 비용은 1이지만 0에서 2를 거쳐 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)이고, 이동 비용은 방향이 바뀌는지에 따라 정합니다.

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

어떤 큐를 선택할까

간선 비용사용할 도구갱신 기준
모두 1BFS의 일반 큐처음 발견한 거리가 최단거리
0 또는 10-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로 표시합니다.

예시

5 6 0
0 1 1
0 2 0
2 1 0
1 3 1
2 3 1
3 2 0
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, 도달 불가를 포함해 검사합니다.

AI로 읽기 · Markdown
Markdown 열기 ↗
curl -fsSL 'https://www.readiz.com/records/zero-one-bfs/index.md'

서비스 열기

열기 방식을 선택해 주세요.

새 브라우저 탭에서 열기현재 화면을 유지하며 별도 탭에서 사용합니다.

로그인이 필요하거나 창 안에서 열리지 않는 서비스는 새 브라우저 탭에서 열어 주세요.