백준 #9019 : DSLR

 

bfs문제였다.

최단경로 => BFS !

 

그리고 path reconstruct할때 reverse하는거 잊지말자!

 

/**
 * @name: DSLR
 * @link: https://www.acmicpc.net/problem/9019
 * @date 2020-04-30
 * @author sunmon
 * TIP: String으로 이용
**/
#include <iostream>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;

int parent[10000];
string DSLR[4] = {"D","S", "L", "R"};

int dslr(int n, int t){
    if(t == 0) return (n<<1) % 10000; 
    else if(t == 1) return (n==0)? 9999: n-1;
    else if(t == 2) return (n%1000)*10 + n/1000;
    else return n/10 + (n%10)*1000;
}

string solve(int a, int b){
    queue<int> q;
    q.push(a);
    parent[a] = a;  //주의! 이거 없으면 무한뺑뺑이 가능
    while(!q.empty()){
        int cur = q.front();
        q.pop();
        if(cur == b) break;
        for(int i = 0; i<4; i++){
            int next = dslr(cur, i);
            if(parent[next]!=-1) continue;
            parent[next] = cur;
            q.push(next);
        }
    }

    //construct
    string path="";
    int cur = b;
    while(cur != parent[cur]){
        int next = parent[cur];
        for(int i = 0; i<4; i++){
            if(dslr(next, i) != cur) continue;
            path += DSLR[i];
            break;
        }
        cur = next;
    }
    reverse(path.begin(), path.end());
    return path;
}

int main(){
    int t;
    cin >> t;
    while(t--){
        memset(parent,-1,sizeof(parent));
        int a, b;
        cin >> a >> b;
        cout << solve(a,b) << "\n";
    }

}