[백준/BOJ] 9019 DSLR

문제 : 9019 DSLR

9019번: DSLR

두 수가 주어졌을 때 어떤 행동을 통해 첫 번째 수를

두 번째 수로 바꾸는 최소 횟수와 그 경로를 출력하는 문제이다.

BFS를 이용해 최소 횟수를 구하면서, 가는 경로를 저장하는

문자열 배열도 만들어 추가로 저장해주면 된다.

나 같은 경우에는 그냥 pair를 활용해 최소 횟수와 경로를

저장하는 배열을 한데 묶어 저장했다. 

---

Code

#include <bits/stdc++.h>
#define ll long long
using namespace std;
typedef pair<ll,string> pls;
ll N, M;
string BFS(){
    string ret;
    vector<pls> arr(10005);
    queue<ll> q;
    arr[N].first=1;
    q.push(N);
    while (!q.empty()){
        ll x=q.front();
        q.pop();
        if (x==M){
            ret=arr[M].second;
            break;
        }
        ll dir[4]={(x*2)%10000, ((x+10000)-1)%10000, (x%1000)*10+x/1000, (x%10)*1000+x/10};
        char c[4]={'D','S','L','R'};
        for (int i=0;i<4;i++){
            if (arr[dir[i]].first==0){
                arr[dir[i]].first=1;
                arr[dir[i]].second=arr[x].second+c[i];
                q.push(dir[i]);
            }
        }
    }
    return ret;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    ll T;
    cin >> T;
    while (T--){
        cin >> N >> M;
        cout << BFS() << "\n";
    }
    return 0;
}