[9019] DSLR

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

9019번: DSLR

<문제>

L 연산은 cur%1000*10으로 d2, d3, d4 3자리를 구성한 뒤 cur/1000을 더해주어서 구현한다.

R연산도 L연산과 마찬가지로 구현해주면 되겠다.

출력해야하는 값, 즉 명령어의 순서를 파악하기 위해서

현재 정점을 {현재 숫자(int), 명령어의 순서(string)}으로 구성했다.

 

<소스코드>

#include <bits/stdc++.h>
using namespace std;
int t, a, b;
bool _visit[10000];
int main(void) {
    cin >> t;
    while (t--) {
        cin >> a >> b;
        queue<pair<int, string>> q;
        q.push({a, ""});
        memset(_visit, false, sizeof(_visit));
        _visit[a] = true;
        while (!q.empty()) {
            pair<int, string> cur = q.front();
            q.pop();
            if (cur.first == b) {
                cout << cur.second << '\n';
                break;
            }
            int D = cur.first * 2 % 10000;
            if (_visit[D] == false) {
                _visit[D] = true;
                q.push({D, cur.second + "D"});
            }
            int S = cur.first - 1;
            if (S == -1) S = 9999;
            if (_visit[S] == false) {
                _visit[S] = true;
                q.push({S, cur.second + "S"});
            }
            int L = (cur.first % 1000) * 10 + (cur.first / 1000);
            if (_visit[L] == false) {
                _visit[L] = true;
                q.push({L, cur.second + "L"});
            }
            int R = 1000 * (cur.first % 10) + cur.first / 10;
            if (_visit[R] == false) {
                _visit[R] = true;
                q.push({R, cur.second + "R"});
            }
        }
    }
    return 0;
}