(9019) DSLR

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

단계별로 풀어보기

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

 

 

 

from배열만 있어도 역추적할 수는 있지만, 수가 아니라 명령을 역추적해야 하므로 편의를 위해 이전 수와 명령어까지 저장했다.

 

 

 

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

void solve(){
  int a, b;
  
  cin >> a >> b;
  
  vector<int> dist(10001, -1);
  vector<pair<int,int>> from(10001, {-1, 0});
  
  queue<int> q;
  
  q.push(a);
  dist[a]= 0;
  
  while(!q.empty()){
    int now= q.front();
    q.pop();
    
    if(now==b)  break;
    
    int now_d= (2*now)%10000;
    if(dist[now_d]==-1){
      dist[now_d]= dist[now]+1;
      from[now_d]= {now, 0};
      q.push(now_d);
    }
    
    int now_s= now>0?now-1:9999;
    if(dist[now_s]==-1){
      dist[now_s]= dist[now]+1;
      from[now_s]= {now, 1};
      q.push(now_s);
    }
    
    int now_l= (now*10)%10000+now/1000;
    if(dist[now_l]==-1){
      dist[now_l]= dist[now]+1;
      from[now_l]= {now, 2};
      q.push(now_l);
    }
    
    int now_r= now/10+(now%10)*1000;
    if(dist[now_r]==-1){
      dist[now_r]= dist[now]+1;
      from[now_r]= {now, 3};
      q.push(now_r);
    }
  }
  
  pair<int,int> x= from[b];
  vector<int> res;
  
  while(x.first>=0){
    res.push_back(x.second);
    x= from[x.first];
  }
  
  for(int i=res.size()-1;i>=0;i--)  cout << "DSLR"[res[i]];
  cout << "\n";
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int T;
  
  cin >> T;
  
  while(T--){
    solve();
  }
  
  return 0;
}