(13913) 숨바꼭질 4

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

단계별로 풀어보기

32단계(동적 계획법과 최단거리 역추적) 6번째

 

 

 

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

int main() {
  int n, k;
  
  cin >> n >> k;
  
  vector<int> dist(100001, -1), from(100001, -1), res;
  
  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;
      from[now-1]= now;
      q.push(now-1);
    }
    
    if(now+1<=100000 && dist[now+1]==-1){
      dist[now+1]= dist[now]+1;
      from[now+1]= now;
      q.push(now+1);
    }
    
    if(2*now<=100000 && dist[2*now]==-1){
      dist[2*now]= dist[now]+1;
      from[2*now]= now;
      q.push(2*now);
    }
  }
  
  cout << dist[k] << "\n";
  
  while(k>=0){
    res.push_back(k);
    k= from[k];
  }
  
  for(int i=res.size()-1;i>=0;i--)  cout << res[i] << " ";
  
  return 0;
}