[BaekJoon] 9019 DSLR :: monton

문제

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

풀이

최소한의 명령어를 나열하라고 하였으므로 bfs를 사용

최소 시간이 아니므로 명령어를 담을 큐도 추가로 구현해 준다

이미 방문했던 숫자는 이미 최소의 명령어가 있다는 의미 이므로

visit 배열을 사용해서 다시 방문하지 않게 해준다

코드

#include<iostream>
#include<queue>
#include<string>
using namespace std;
 
int A, B;
int visit[10000];
 
int main() {
    int T;
    cin >> T;
 
    for (int t = 0; t < T; t++) {
        cin >> A >> B;
        queue<int> qx;
        queue<string>qs;
        qx.push(A), qs.push("");
 
        for (int i = 0; i < 10000; i++) visit[i] = 0;
        visit[A] = 1;
 
        while (!qx.empty()) {
            int x = qx.front();
            string s = qs.front();
            qx.pop(), qs.pop();
 
            if (x == B) {
                cout << s << endl;
                break;
            }
 
            for (int i = 0; i < 4; i++) {
                string str = s;
                int nx = x;
                if (i == 0) {
                    nx *= 2;
                    str += 'D';
                }
                else if (i == 1) {
                    nx -= 1;
                    str += 'S';
                }
                else if (i == 2) {
                    int num = nx / 1000;
                    nx = (nx % 1000) * 10 + num;
                    str += 'L';
                }
                else { 
                    int num = (nx % 10) * 1000;
                    nx = (nx / 10) + num;
                    str += 'R';
                }
 
                nx = nx >= 10000 ? nx%10000 : nx;
                nx = nx == -1 ? 9999 : nx;
                
                if (visit[nx]) continue;
 
                qx.push(nx), qs.push(str);
                visit[nx] = 1;
            }
        }
    }
}