0-1 BFS(deque, Dijkstra)

[devLupin]

• 가중치가 0 또는 1인 그래프에서 최단거리 찾기
• 일반적인 BFS로는 풀이할 수 없다.

BFS의 한계

• queue의 앞쪽에서 뒤로 순차적으로 쌓는다.
  • 그래서, 가중치가 1일 때만 가능
  • 가중치가 2개 이상이면 순서를 보장받을 수 없으므로..

[devLupin]

0-1 BFS using deque

• deque는 queue와 stack을 합친 느낌의 자료구조라고 볼 수 있음.
  • push_back과 push_front와 같은 함수 지원

• 구현

  • deque의 앞쪽부터 pop
  • 가중치가 0인 경우 push_front()
  • 더 우선적으로 처리되어야 하므로
  • 가중치가 1인 경우 push_back()

    
    auto cur = dq.front();
    dq.pop_front();

  if(weight = 0 && !visited) dq.push_front(next) else dq.push_back(next)

[devLupin]

Dijkstra Algorithm

• priority queue(a.k.a min heap) 이용
• greater<pair<int,int>>를 사용하려면 가중치가 first가 되어야 함.
• 가중치가 여러 개여도 사용가능
  • deque와 달리 모든 원소에 정렬을 적용하므로

• 구현

  typedef pair<int.int> pii;
  priority_queue<pii, vector<pii>, greater<pii>> pq;
  
  pii cur = pq.top();
  pq.pop();
  
  if(!visited)
  pq.push(next)