0-1 BFS

특정한 상황에 놓인 그래프에서 최단 경로를 찾을 때 O(V+E)의 시간 복잡도로 해결할 수 있는 0-1 BFS에 대해 알아보자.

0-1 BFS란

가중치가 0과 1로만 주어진 그래프에서 최단 경로를 찾고자 할 때 BFS를 응용하여 풀 수 있다.

보편적으로 사용하는 다익스트라 알고리즘의 시간 복잡도가 O(E log E)혹은 O(E log V)인데 0-1 BFS를 사용하면 단지 O(V+E)의 선형 시간 복잡도로 문제를 해결할 수 있기 때문이다.

0-1 BFS의 동작

왜 0-1 BFS가 O(V+E)에 동작할 수 있을까?

이는 BFS에서 노드를 관리하기 위해 큐를 사용하는 대신 덱(deque)을 사용하여 실현할 수 있다.

 

0-1 BFS는 다음 과정에 따라 최단 경로를 찾게 된다.

1. 덱의 front에서 현재 노드를 꺼낸다.
2. 연결된 인접 노드를 살펴본다.
3. 현재 노드까지 소비된 비용 + 그 노드를 향하는 가중치 < 그 노드까지 가는데 소비된 비용이면 소비된 비용을 갱신해준다.
4. 노드가 갱신된 상태에서 만약 그 노드를 향하는 가중치가 0이면 덱의 front, 1이면 덱의 back에 삽입하도록 한다.
5. 덱에서 더 이상 꺼낼 노드가 없을 때까지 이 과정을 반복한다.

O(V+E) 증명

0-1 BFS를 수행하면 가중치가 1인 간선을 0번 거쳐간 노드 -> 가중치가 1인 간선을 1번 거쳐간 노드 -> ... -> 가중치가 1인 간선을 E번 거쳐간 노드

 

이런 식으로 비용이 적은 경로부터 탐색을 하기 때문에 특정 간선을 2번 이상 지나가는 경우는 없다. O(E)

똑같이 모든 정점도 2번 이상 경유하는 경우가 없으므로 덱 크기는 최대 |V|이다. O(V)

따라서 0-1 BFS는 O(V) + O(E) = O(V+E)의 시간 복잡도를 가지게 된다.

In Graph

그래프 간선의 가중치를 0 또는 1이라고 가정, 한 정점에서 다른 정점들까지의 최단 경로를 구해보자. 작동 방식은 다음과 같다.

1. 시작 정점은 k, 정점 k로부터 정점 i까지의 최단 거리를 d𝚒라고 한다.
2. 정점 x에서 정점 y로 가는 가중치 z인 간선이 존재할 때 w(x,y) = z라고 한다.
3. d𝘬는 0, 나머지 d𝚒는 모두 ∞로 초기화한다.
4. 빈 덱에 정점 k를 추가한다.
5. 덱의 맨 앞에서 정점 하나를 뺀다. 이 정점을 u라고 하자.
6. u가 아직 선택되지 않았으면, u를 선택하고 u와 인접한 정점을 확인한다. u와 인접한 각각의 정점 v에 대해 d𝑢 + w(u,v) < d𝚟일 때, d𝚟를 d𝑢 + w(u,v) 로 바꾼 다음 w(u,v) = 0인 경우 v를 덱의 맨 앞에 추가하고 w(u,v) = 1인 경우 v를 덱의 맨 뒤에 추가한다. 쉽게 말하면, 현재 노드까지 소비된 비용 + 그 노드를 향하는 가중치 < 그 노드까지 가는데 소비된 비용 이면 소비된 비용을 갱신한다. 이 때 노드를 향하는 가중치가 0이면 덱의 맨 앞에, 가중치가 1이면 덱의 맨 뒤에 추가한다.
7. 덱이 빈 경우 실행을 종료한다. 그렇지 않은 경우 5번으로 돌아간다.

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

---

 

다음과 같은 무향 그래프(간선에 방향성이 없는 그래프)에서 최단 경로를 찾는 경우를 생각해 보자. 시작 정점은 I이다.

D : []

 

처음에 덱에 정점 I가 추가되고, 바로 빠진 다음 I와 인접한 정점들을 확인한다. 이 과정에서 덱의 앞에 정점 H가, 덱의 뒤에 정점 C,G가 추가된다. (가중치가 0인 정점을 덱의 앞에, 가중치가 1인 정점을 덱의 뒤에 삽입한다.)

D : [H C G]

 

 

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

D : [C G E F]

 

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

D : [B G E F]

 

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

D : [G E F A D]

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

D : [A E F A D]

 

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

D : [E F A D]

 

다음으로 정점 E가 덱에서 빠지고 E와 인접한 정점들을 확인한다. 정점 D가 덱의 맨 앞에 추가된다.

D : [D F A D]

 

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

관련 문제

https://www.acmicpc.net/problem/13549

13549번: 숨바꼭질 3

https://www.acmicpc.net/problem/1261

1261번: 알고스팟