콘텐츠로 이동

0-1 BFS

가중치 없는 그래프에서는 너비 우선 탐색을 사용하여 하나의 시작점에서 다른 모든 정점까지의 최단 경로를 $O(|E|)$에 찾을 수 있다는 것이 잘 알려져 있습니다. 즉, 거리는 시작점에서 다른 정점까지 가기 위해 지나야 하는 간선의 최소 개수입니다. 이러한 그래프는 모든 간선의 가중치가 $1$인 가중치 그래프로도 해석할 수 있습니다. 그래프의 모든 간선이 같은 가중치를 갖지 않는다면, $O(|V|^2 + |E|)$ 또는 $O(|E| \log |V|)$ 시간에 동작하는 Dijkstra와 같은 더 일반적인 알고리즘이 필요합니다.

그러나 가중치에 더 강한 제약이 있다면, 대개 더 나은 방법을 쓸 수 있습니다. 이 글에서는 각 간선의 가중치가 $0$ 또는 $1$일 때 BFS를 사용하여 SSSP(단일 시작점 최단 경로) 문제를 $O(|E|)$에 푸는 방법을 보여 드립니다.

알고리즘

Dijkstra 알고리즘을 면밀히 살펴보고, 우리가 다루는 특수한 그래프에서 어떤 결과가 따라 나오는지 생각해 보면 알고리즘을 만들어 낼 수 있습니다. Dijkstra 알고리즘의 일반적인 형태는 다음과 같습니다(여기서는 우선순위 큐로 set을 사용합니다):

d.assign(n, INF);
d[s] = 0;
set<pair<int, int>> q;
q.insert({0, s});
while (!q.empty()) {
    int v = q.begin()->second;
    q.erase(q.begin());

    for (auto edge : adj[v]) {
        int u = edge.first;
        int w = edge.second;

        if (d[v] + w < d[u]) {
            q.erase({d[u], u});
            d[u] = d[v] + w;
            q.insert({d[u], u});
        }
    }
}

시작점 s로부터 큐에 있는 임의의 두 정점까지의 거리는 최대 1만큼만 차이가 난다는 것을 알 수 있습니다. 특히, 각 $u \in Q$에 대하여 $d[v] \le d[u] \le d[v] + 1$임을 알 수 있습니다. 그 이유는 각 반복에서 큐에 추가하는 정점이 거리가 같거나 거리가 1 더 큰 정점뿐이기 때문입니다. 큐에 $d[u] - d[v] > 1$인 $u$가 존재한다고 가정하면, $u$는 $d[t] \ge d[u] - 1 > d[v]$인 다른 정점 $t$를 통해 큐에 삽입되었어야 합니다. 그러나 Dijkstra 알고리즘은 정점을 증가하는 순서로 순회하므로 이는 불가능합니다.

즉, 큐의 순서는 다음과 같은 모습입니다:

$$Q = \underbrace{v}_{d[v]}, \dots, \underbrace{u}_{d[v]}, \underbrace{m}_{d[v]+1} \dots \underbrace{n}_{d[v]+1}$$

이 구조는 매우 단순하므로 실제 우선순위 큐가 필요하지 않습니다. 즉, 균형 이진 트리를 사용하는 것은 과한 선택입니다. 큐에는 서로 다른 거리가 두 가지만 존재하므로, 이를 두 개의 벡터에 나누어 보관할 수 있습니다. $q_0$에는 거리가 $d[v]$인 정점을, $q_1$에는 거리가 $d[v] + 1$인 정점을 담습니다. 가중치가 $0$인 간선은 $q_0$에, 가중치가 $1$인 간선은 $q_1$에 정점을 추가합니다. $q_0$이 비게 되면 현재 거리의 모든 정점이 처리된 것이므로, 두 벡터를 맞바꾸고 현재 거리는 1 증가합니다.

vector<int> d(n, INF);
d[s] = 0;
vector<int> q0, q1;
q0.push_back(s);
while (!q0.empty()) {
    int v = q0.back();
    q0.pop_back();
    for (auto edge : adj[v]) {
        int u = edge.first;
        int w = edge.second;
        if (d[v] + w < d[u]) {
            d[u] = d[v] + w;
            if (w == 0)
                q0.push_back(u);
            else
                q1.push_back(u);
        }
    }
    if (q0.empty())
        swap(q0, q1);
}

이렇게 작성하면 두 단계가 명시적으로 드러납니다. 정점은 현재 거리에서 도달하면 $q_0$에, 한 단계 더 먼 거리에서 도달하면 $q_1$에 추가되므로, 위에서 본 $Q$의 구조를 손수 유지할 필요 없이 코드 자체에 녹아 있게 됩니다. $q_1$에 추가된 뒤 현재 거리로 갱신된 정점은 예전 사본을 남기지만, 이 낡은 사본은 해가 되지 않습니다. 나중에 꺼내졌을 때 d[v] + w < d[u] 검사에서 더 갱신할 것이 없기 때문입니다. $q_0$은 큐가 아니라 스택으로 사용된다는 점에 유의하십시오. 하지만 이는 문제가 되지 않습니다. $q_0$의 모든 정점은 거리가 같으므로 처리 순서는 상관이 없습니다.

같은 알고리즘은 하나의 deque를 사용하여 가중치가 $0$이면 앞에, $1$이면 뒤에 넣는 방식으로 더 흔히 작성되며, 이때 push_front와 push_back이 각각 $q_0$과 $q_1$의 역할을 합니다. 실제로는 두 개의 벡터를 사용하는 편이 더 좋습니다. 덱의 청크 단위 저장 방식을 피할 수 있기 때문입니다. 캐시에 들어갈 만큼 작은 그래프에서는 약 $1.15$배 빠르게 측정되며, 정점이 수백만 개인 그래프에서는 대략 $1.06$배로 줄어듭니다. 이런 그래프에서는 메모리 지연 시간이 지배적이어서 컨테이너 선택이 훨씬 덜 중요합니다(벤치마크 참조).

가중치가 $0$인 간선이 하나도 없다면 이 알고리즘은 일반적인 BFS로 퇴화하며, 이 경우에는 단순한 BFS가 더 간단하고 약간 더 빠릅니다.

Dial 알고리즘

간선의 가중치가 더 커지는 것을 허용하면 이를 더욱 확장할 수 있습니다. 그래프의 모든 간선의 가중치가 $\le k$라면, 큐에 있는 정점들의 거리는 시작점에서 $v$까지의 거리와 최대 $k$만큼 차이가 납니다. 따라서 큐에 있는 정점들을 위해 $k + 1$개의 버킷을 유지하고, 가장 작은 거리에 해당하는 버킷이 빌 때마다 순환 이동을 하여 그다음으로 큰 거리의 버킷을 얻을 수 있습니다. 이 확장을 Dial 알고리즘이라고 합니다.

연습 문제