[그래프] 0-1 BFS 알고리즘

작성일 | In

어제 알고리즘에 대해 검색을 하다가 코드포스 블로그에서 흥미로운 최단경로 최적화법을 찾아서, 그 방법을 소개하고자 합니다.

선수 조건

이 알고리즘을 이해하기 위해서는 몇 가지를 알아야 합니다.

  1. 기본적인 그래프 이론
  2. BFS
  3. 최단경로 알고리즘

해결할 문제

그래프 G에 V개의 정점과 E개의 간선이 있습니다.
이 그래프는 가중치 그래프지만, 가중치는 0 또는 1입니다.
이 그래프에서 최단 경로를 찾는 효율적인 코드를 작성하세요.

Naive Solution : 다익스트라 알고리즘

다익스트라는 이진 힙을 사용하면 O(ElogV), 피보나치 힙을 사용하면 O(E + VlogV)의 시간복잡도를 갖습니다.
휴리스틱을 이용해 시도할 수도 있겠지만, 최악의 경우에는 딱히 효과적이지 않습니다.
이 시점에서 여러분들은 두 가지를 궁금해 할 것입니다.

  1. 다익스트라 알고리즘을 어떻게 최적화 할 것 인가
  2. 왜 다익스트라같은 효율적인 알고리즘을 단순한 솔루션이라고 적었는가

답변은 다음과 같습니다.

  1. 이번에 소개할 효율적인 알고리즘은 다익스트라 알고리즘을 최적화 시킨 것이 아닙니다.
  2. 다익스트라 알고리즘을 알고 있는 거의 모든 사람은 이 질문을 처음 본 경우 다익스트라를 선택합니다.

여러분들이 다익스트라가 최선의 코드라고 생각한다면, 저는 여러분들께

  1. 매우 간단하며
  2. 이 유형의 그래프 문제를 효율적으로 해결할 수 있는

BFS를 이용한 아름다운 기법을 소개하고자 합니다.

이 알고리즘을 학습하기 전에, 나중에 명료하게 이해할 수 있는 보조 정리가 필요합니다.
보조 정리 : BFS를 실행하는 동안에는, 정점을 포함하는 큐에는 BFS트리의 최대 두 개의 연속한 레벨의 요소만 포함할 수 있습니다.
증명 : BFS트리는 그래프에서 BFS를 실행하는 동안 만들어진 트리입니다. BFS는 인접한 정점으로만 이동하므로 큐의 모든 정점은 다른 모든 정점까지 최대 하나의 레벨만 차이나기 때문에 위 보조 정리는 참입니다.

Optimize Solution : 0-1BFS

이 알고리즘은 간선의 가중치가 0 또는 1인 그래프에서 작동하기 때문에 0-1BFS라고 불립니다.
간선의 가중치가 0 또는 1인 임의의 정점 u에 BFS를 실행해봅시다.
다익스트라처럼 큐에는 오직 이전 정점을 통해 최단 거리가 줄어든 정점만 큐에 삽입합니다.
그러면서 동시에 큐는 항상 시작점으로부터의 거리에 대해 정렬된 상태입니다.

이제, 우리는 u 정점에 있습니다. 간선(u, v)를 지날 때, 우리는 두 가지 경우 중 한 가지가 일어나는 것을 확신할 수 있습니다.

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

간선의 가중치가 0 또는 1이기 때문에 위 두 가지 경우만 나오게 됩니다. 다시 말해,

  1. 가중치가 0이라는 것은 v는 u와 같은 레벨이다.
  2. 가중치가 1이라는 것은 v는 u의 1레벨 아래이다.

또한 우리는 이미 BFS 실행 중에는 큐에 있는 정점은 최대 2가지의 레벨로만 이루어져 있는것을 알 수 있습니다.

그러므로 만약 우리가 u정점에 있다면, 큐는 레벨이 L[u] 또는 L[u]+1인 정점만 들어있습니다.
그리고, 간선(u, v)에 대해, L[v]는 L[u] 또는 L[u]+1입니다.
그러므로, v정점이 u에 의해 최단거리가 단축되었고, u와 같은 레벨이라면 큐의 앞 부분에 v를 삽입합니다.
반대의 경우에는 큐 뒷부분에 삽입합니다.
이 행위는 BFS가 제대로 작동하기 위해 큐가 정렬된 상태를 유지하는 것을 도와줍니다.

하지만, 일반적인 큐 구조를 사용하면 삽입과 정렬된 상태를 유지하는 것을 O(1)만에 수행하지 못합니다.
우선순위큐(Priority Queue)는 정렬된 상태를 유지하는데 O(logN)을 소모합니다.
일반적인 큐의 문제는 다음 3가지 기능을 수행하는데 도움이 되는 메소드가 없다는 것입니다.

  1. 다음 정점 추출하기(BFS를 위해 정점 추출)
  2. 가장 앞쪽에 삽입하기(같은 레벨의 정점 삽입)
  3. 가장 뒤쪽에 삽입하기(다른 레벨의 정점 삽입)

다행스러운건, 덱(Deque, Double Ended Queue)이라는 자료구조가 모든 기능을 제공합니다.

의사 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
    for all v in verticces:
        dist[v] = inf
    dist[start] <- 0
    deque d
    d.push_front(start)

    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)

보다시피 이 알고리즘은 BFS나 다익스트라와 유사합니다.
하지만 이 코드의 시간복잡도는 선형 시간이고, 다익스트라보다 훨씬 효율적인 O(E + V)입니다.

[출처] https://codeforces.com/blog/entry/22276

여기까지가 코드포스에 올라온 글의 번역입니다.

시간 복잡도 분석

시간복잡도를 유도해봅시다.
d에는 최대 O(V)개의 정점이 들어갑니다. 그러므로 while문은 O(V)번 반복합니다.
deque에서 pop을 하는것은 O(1)안에 완료됩니다.
while문 안에 있는 for문은 deque에서 추출한 정점과 인접한 모든 정점의 개수만큼 반복합니다. O(Evertex)번 반복합니다.
if-else문은 O(1)안에 완료됩니다.

이제 총 시간복잡도를 구해봅시다.
O(V) * { O(1) + O(Evertex) + O(1) }
= O(V) + O(V * Evertex) + O(V) 인데, V * Evertex 는 전체 간선의 개수와 같습니다. 그러므로 다음과 같이 수정할 수 있습니다.
O(2V) + O(E)
= O(V) + O(E)
= O(V + E)
최종적으로 O(V + E)가 나오게 됩니다.