[알고리즘] 0-1 BFS

edge가 0 혹은 1의 가중치를 가질 때 사용하는 bfs이다. 

 

사용하는 자료 구조

- 덱

 

접근

- 다익스트라 알고리즘을 최적화시킨 것이다. 사실 다익스트라 써도 상관없다. 다익스트라도 가중치 있는 노드에서 최단 거리 찾는 알고리즘이기 때문.

- 가중치가 0이라는 것은 이전 노드와 동일 레벨이 존재한다는 것이다. 가중치가 1이면 이전노드에 비해 한 레벨 아래에 존재한다는 의미.

- 가중치가 0인 것을 우선으로 팝하기 위해 가중치가 0인 경우 큐 앞쪽에, 가중치가 1인 경우 큐 뒤쪽에 푸쉬한다. 하지만 일반적인 큐는 앞에 푸쉬하는 것이 불가능하기 때문에 덱을 사용해서 앞쪽에 푸쉬한다.

 

#include <deque>

int main(void){
	deque<int> dq;
    
    dq.push_front(시작노드);
    while(!dq.empty()){
    	int fr = dq.front();
        dq.pop_front();
        for fr의 인접 노드 중에:
          if(가중치가 0이면){
              q.push_front(현재 노드);
          }

          else if(가중치가 1이면){
              q.push_back(현재노드);
          }
    }
}