119. 0-1 BFS

$0$-$1$ BFS는 모든 간선의 가중치가 $0$ 또는 $1$인 그래프에서 사용할 수 있는 최단 경로 알고리즘으로, 한 정점에서 다른 정점들까지의 최단 경로를 구한다. 작동 방식은 다음과 같다.

    1. 시작 정점은 $k$, 정점 $k$로부터 정점 $i$까지의 최단 거리를 $d_i$라고 한다.

    2. 정점 $x$에서 정점 $y$로 가는 가중치 $z$인 간선이 존재할 때 $w(x, y) = z$라고 한다.

    3. $d_k$는 $0$, 나머지 $d_i$는 모두 $\infty$로 초기화한다.

    4. 빈 덱에 정점 $k$를 추가한다.

    5. 덱의 맨 앞에서 정점 하나를 뺀다. 이 정점을 $u$라고 하자.

    6. $u$가 아직 선택되지 않았으면, $u$를 선택하고 $u$와 인접한 정점을 확인한다. $u$와 인접한 각각의 정점 $v$에 대해, $d_u + w(u, v) < d_v$일 때 $d_v$를 $d_u + w(u, v)$로 바꾼 다음 $w(u, v) = 0$인 경우 $v$를 덱의 맨 앞에 추가하고 $w(u, v) = 1$인 경우 $v$를 덱의 맨 뒤에 추가한다.

    7. 덱이 빈 경우 실행을 종료한다. 그렇지 않은 경우 5번으로 돌아간다.

 

각각의 과정에서 덱에 포함된 정점들의 $d_i$ 값은 모두 동일하거나, 아니면 연속한 두 정수 중 하나와 같다.

---

다음과 같은 무향 그래프에서 최단 경로를 찾는 경우를 생각해 보자. 시작 정점은 $\text{I}$이다.

$D: [\ ]$

 

처음에 덱에 정점 $\text{I}$가 추가되고, 바로 빠진 다음 $\text{I}$와 인접한 정점들을 확인한다. 이 과정에서 덱의 앞에 정점 $\text{H}$가, 덱의 뒤에 정점 $\text{C}$와 $\text{G}$가 추가된다.

$D: [\text{H}\ \text{C}\ \text{G}]$

 

다음으로 정점 $\text{H}$가 덱에서 빠지고, $\text{H}$와 인접한 정점들을 확인한다. 정점 $\text{E}$와 $\text{F}$가 덱의 뒤에 추가된다.

$D: [\text{C}\ \text{G}\ \text{E}\ \text{F}]$

 

다음으로 정점 $\text{C}$가 덱에서 빠지고, $\text{C}$와 인접한 정점들을 확인한다. 정점 $\text{B}$가 덱의 앞에 추가된다.

$D: [\text{B}\ \text{G}\ \text{E}\ \text{F}]$

 

다음으로 정점 $\text{B}$가 덱에서 빠지고, $\text{B}$와 인접한 정점들을 확인한다. 정점 $\text{A}$와 $\text{D}$가 덱의 뒤에 추가된다.

$D: [\text{G}\ \text{E}\ \text{F}\ \text{A}\ \text{D}]$

 

다음으로 정점 $\text{G}$가 덱에서 빠지고, $\text{G}$와 인접한 정점들을 확인한다. 정점 $\text{A}$가 덱의 앞에 추가된다.

$D: [\text{A}\ \text{E}\ \text{F}\ \text{A}\ \text{D}]$

 

다음으로 정점 $\text{A}$가 덱에서 빠지고, $\text{A}$와 인접한 정점들을 확인한다. 덱에 아무 정점도 추가되지 않는다.

$D: [\text{E}\ \text{F}\ \text{A}\ \text{D}]$

 

다음으로 정점 $\text{E}$가 덱에서 빠지고, $\text{E}$와 인접한 정점들을 확인한다. 정점 $\text{D}$가 덱의 앞에 추가된다.

$D: [\text{D}\ \text{F}\ \text{A}\ \text{D}]$

 

이 다음부터는 덱에 더 이상 정점이 추가되지 않는다. 덱에 있는 네 개의 정점이 모두 빠진 후 실행이 종료된다.

 

구현은 다음과 같다. 0-1 BFS의 경우, 각각의 정점은 덱에 최대 두 번 들어갔다 나오고, 각각의 간선은 무향 그래프를 기준으로 하면 두 번씩 확인하므로 시간복잡도는 일반 DFS, BFS와 같은 $\Theta(n+m)$이다.

#import<bits/stdc++.h>
using namespace std;
int d[100005];
vector<pair<int, int>>e[100005];
deque<int>D;
int main()
{
    int k, m, n, x, y, z;
    cin >> n >> m >> k;
    for(int i = 1; i <= m; i++)
    {
        cin >> x >> y >> z;
        e[x].push_back({y, z});
        e[y].push_back({x, z});
    }
    fill(d + 1, d + n + 1, 1 << 30);
    d[k] = 0;
    for(D.push_back(k); D.size();)
    {
        int u = D.front();
        D.pop_front();
        for(auto &p: e[u])
        {
            int v = p.first;
            if(d[u] + p.second < d[v])
            {
                d[v] = d[u] + p.second;
                if(p.second)D.push_back(v);
                else D.push_front(v);
            }
        }
    }
}

이 구현은 앞에서 설명한 방법과 약간 다른데, 이 코드에서는 이미 확인한 정점을 또 확인하게 된다. 덱에 각각의 정점이 최대 두 번만 들어가기 때문에 이렇게 구현해도 대부분의 문제를 풀 때는 지장이 없지만, 덱에서 같은 정점이 두 번째 빠질 때도 인접한 정점을 모두 확인하기 때문에 각각의 간선을 최대 네 번까지 확인하게 되며 시간이 두 배로 많이 걸린다. 각각의 정점을 방문했는지 체크하는 등의 방법으로 이것을 피할 수 있다.

 

[연습문제]

 

BOJ 13549. 숨바꼭질 3 (Gold V)

순간이동을 하는 경우를 가중치가 $0$인 간선을 거치는 것으로, 걷는 경우를 가중치가 $1$인 간선을 거치는 것으로 간주하면 0-1 BFS를 쓸 수 있는 형태가 된다.

 

CF 1340C. Nastya and Unexpected Guest (2400)

현재까지 초록불이 켜진 횟수를 기준으로 각각의 땅에 대해 0-1 BFS를 실행한다.

 

→ solved.ac tag: 0_1_bfs