0 - 1 BFS

 

0-1 BFS - Algorithms for Competitive Programming

 

그래프의 모든 edge의 weight가 동일하다면 BFS로 O( \( |E| \) )만에 한 source에서 다른 모든 vertex들까지의 거리를 구할 수 있다.

 

반면 모든 edge의 weight가 동일하지 않다면 Dijkstra's algorithm을 통해 O( \( |E|log|V| \) ) 만에 거리를 구할 수 있다.

 

 

만약 edge의 weight가 0이나 1이라면 어떨까.

 

이 때 사용할 수 있는 방법이 0 - 1 BFS 이다.

 

complexity는 O( \( |E| \) ) 이다.

 

 

결국 구현은 Dijkstra's algorithm과 같다.

 

그러나 현재의 vertex를 구하는 방법으로 Dijkstra는 priority_queue를 썼다면 여기서는 그냥 deque를 쓴다.

 

특정 한 vertex에서 다른 vertex로 가는 edge가 존재할 때 거리가 0이나 1만큼밖에 증가하지 않는다는 관찰을 사용한다.

 

 

모든 거리를 INF로 초기화 시켜준다.

 

source vertex의 거리를 0으로 만들고 source vertex를 빈 deque에 넣는다.

 

deque의 front에서 vertex A를 꺼낸다. ( * )

 

vertex A와 edge가 이어진 모든 vertex B를 하나하나 확인하며 vertex B의 거리가 줄어든다면 아래의 조건을 확인한다.

 

 - edge의 weight가 0이라면 deque의 앞에 넣고 weight가 1이라면 deque의 뒤에 넣는다.

 

위 과정( * )을 deque가 빌때까지 반복한다.

 

 

이를 응용한 Dial's algorithm이라는 것도 있다고 한다.

 

weight가 k 이하일 때, k + 1개의 bucket을 만들어서 위처럼 하는 알고리즘이다.

(0번째는 거리 + 0, 1번째는 거리 + 1, ..., k번째는 거리 + k vertex를 넣음)

 

i번째 bucket을 다 썼다면 bucket을 shift해서 i + 1번째 bucket부터 다시 시작한다.

(모듈러 연산하면 되겠다)

 

생각보다 구현은 쉬울 것 같은데 O( \( |E| \) ) 만큼 걸린다는 것이 매력적인 알고리즘인듯 하다.