(1697) 숨바꼭질

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

단계별로 풀어보기

27단계(그래프와 순회) 10번째

 

 

 

간혹 거리 탐색을 10만까지만 해도 정답이 나오는지 의문을 제기하는 경우가 있는데, 제대로 된 증명은 아니지만 간단하게 설명하면

50001 → 100002 → 100001 → 100000 (3초)

50001 → 50000 → 100000 (2초)

이렇게 10만을 넘어가는 좌표를 방문하면서 최단 경로인 경우는 없으므로 거리 배열을 10만까지만 설정해도 된다.

 

 

 

#include <iostream>
#include <queue>
using namespace std;

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