(13549) 숨바꼭질 3

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

단계별로 풀어보기

29단계(최단 경로) 3번째

 

 

 

숨바꼭질과 비슷하지만, 2x로 이동하는 순간이동의 소요 시간이 1초에서 0초로 바뀌었다.

다익스트라로 풀 수도 있지만, 가중치가 0과 1밖에 없는 특수한 그래프라면 더 효율적인 0-1 BFS를 쓸 수 있다.

다익스트라가 O(E log max(V, E))인 반면 0-1 BFS는 O(V+E)로 선형 시간 복잡도를 갖는다.

0-1 BFS는 큐 대신 덱을 사용한다. 덱의 앞에서 원소를 하나씩 뽑아 가중치가 1인 간선으로 이어진 이웃한 정점의 거리를 갱신하고 덱의 뒤에 다음 정점을 삽입하는 것 까지는 BFS와 같지만,

가중치가 0인 간선으로 이어졌다면 그 이웃한 정점은 현재 정점과 같은 레벨이므로 덱의 맨 앞에 삽입하여 다른 정점보다 빨리 탐색할 수 있도록 한다.

 

 

 

#include <iostream>
#include <deque>
#include <vector>
using namespace std;

int main() {
  int n, k;
  
  cin >> n >> k;
  
  vector<int> dist(100001, -1);
  
  deque<int> dq;
  
  dq.push_back(n);
  dist[n]= 0;
  
  while(!dq.empty()){
    int now= dq.front();
    dq.pop_front();
    
    if(now==k)  break;
    
    if(2*now<=100000 && dist[2*now]==-1){
      dist[2*now]= dist[now];
      dq.push_front(2*now);
    }
    
    if(now-1>=0 && dist[now-1]==-1){
      dist[now-1]= dist[now]+1;
      dq.push_back(now-1);
    }
    
    if(now+1<=100000 && dist[now+1]==-1){
      dist[now+1]= dist[now]+1;
      dq.push_back(now+1);
    }
  }
  
  cout << dist[k];
  
  return 0;
}