[C++] DSLR (백준 9019번)

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

 

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

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t;
    cin >> t;

    while (t--) {
        int start, end;
        cin >> start >> end;

        vector<bool> vst(10000, false);
        queue<pair<int, string>> q;
        q.emplace(start, "");
        vst[start] = true;
        while (!q.empty()) {
            int curi = q.front().first;
            string curs = q.front().second;
            int nxti;
            q.pop();
            if (curi == end) {
                cout << curs << '\n';
                break;
            }
            // D
            nxti = (2 * curi) % 10000;
            if (!vst[nxti]) {
                q.emplace(nxti, curs + "D");
                vst[nxti] = true;
            }
            // S
            nxti = curi - 1;
            if (nxti < 0) nxti = 9999;
            if (!vst[nxti]) {
                q.emplace(nxti, curs + "S");
                vst[nxti] = true;
            }
            // L
            nxti = (curi * 10) % 10000;
            nxti += curi / 1000;
            if (!vst[nxti]) {
                q.emplace(nxti, curs + "L");
                vst[nxti] = true;
            }
            // R
            nxti = (curi % 10) * 1000;
            nxti += curi / 10;
            if (!vst[nxti]) {
                q.emplace(nxti, curs + "R");
                vst[nxti] = true;
            }
        }
    }
}

문제를 어떤식으로 풀어야 하는지 감이 안 잡혀서 태그도 까고 구글링으로 힌트도 좀 얻었다. 너비 우선 탐색으로 상하좌우로 움직이는 전형적인 문제들과 비슷하게, 너비 우선 탐색으로 D, S, L, R 연산을 하면서 결과를 만들어 내면 된다. 너비 우선 탐색을 해야한다는 것과 각각의 결과에서 D, S, L, R 연산을 수행할 수 있다는 것만 알면 쉽게 풀 수 있는 문제였다. 그걸 떠올리는 게 어려웠지만.. (AC)