0-1 BFS

Problem

$V$ 정점과 $E$ 간선들을 가지고 있는 그래프 $G$가 있다고 가정하자. 이 그래프의 간선들은 0과 1의 가중치를 가지고 있다. $source$ 로부터 가장 짧은 거리를 계산할 수 있는 효율적인 코드를 작성하라.

Naive Solution

---

위의 문제에서 나이브한 솔루션으로는 다익스트라 알고리즘이다. 다익스트라 알고리즘은 $O(E+VlogV)$의 시간 복잡도를 가지지만 모든 상황에서 빠르지 않다.

0-1 BFS 이해

---

이름에서 알 수 있듯이 간선들의 가중치가 0또는 1일때만 사용가능한 알고리즘이다.
기본적인 방법은 다익스트라 처럼 이전 정점에서 최단 거리가 줄어든 정점을 큐에 삽입하는 방법이다.
우리가 임의의 정점 $u$에 있을 때, 연결된 정점 $v$는 두 가지 경우를 가진다. (간선의 가중치는 0 또는 1이기 때문)

1. $v$는 $u$와 같은 레벨이다.
2. $v$는 $u$보다 1 레벨 아래이다.

또한, 우리는 BFS를 하는 동안 큐에 두 가지 레벨만을 유지하는 것도 알 수 있다.

1. $L[v]=L[u]$
2. $L[v]=L[u]+1$

이제 deque를 사용해서 간선 $(u,v)$에 대해 다음의 작업을 진행한다.

1. 최단거리가 줄어들었고 같은 레벨이라면, deque 앞에 정점 $v$를 삽입한다.
2. 다음 레벨이라면, deque 뒤에 정점 $v$를 삽입한다.
   • 일반적인 queue를 사용하면 양쪽 삽입과 정렬을 $O(1)$에 할 수 없고, priority queue는 정렬에만 $O(logN)$의 시간 복잡도를 가지기 때문에 적절하지 않다. 따라서 deque를 사용하는 것이다.

다음은 구현하기 위한 수도코드이다.

for all v in vertices:
    dist[v] = inf
dist[source] = 0;
deque d
d.push_front(source)
while d.empty() == false:
    vertex = get front element and pop as in BFS.
    for all edges e of form (vertex , u):
        if travelling e relaxes distance to u:
            relax dist[u]
            if e.weight = 1:
                d.push_back(u)
            else:
                d.push_front(u)

관련된 문제로는 백준의 숨박꼭질 3이다.

0-1 BFS의 성능

---

코드 자체는 BFS와 다익스트라를 섞은 것처럼 보이지만, 다익스트라보다 더 효율적인 $O(E+V)$의 시간 복잡도를 가진다.

Reference

---

0-1 BFS [Tutorial] - Codeforces