백준 9019 DSLR (C++)

9019번: DSLR

bfs를 이용한 문제이다. 우선 문제에서 주어지는 D, S, L, R을 각각 구현해주었다. 그 후 bfs를 통해 A = B가 되는 시점을 찾아 출력해주었다. 가장 먼저 A = B가 되는 시점이 최소한인 시점이므로 바로 출력해주었다.
처음 L과 R을 구현할 때 string으로 변환 후 다시 int로 바꾸어주는 식으로 구현했더니 시간 초과가 발생했다. 자릿수 회전은 int형으로 구현 가능한 점을 기억해두자.

#include <iostream>
#include <cstring>
#include <queue>

using namespace std;

int T, A, B;
bool visit[10000];
string res;

int D(int n) {
    n *= 2;

    if (n > 9999) {
        n %= 10000;
    }

    return n;
}

int S(int n) {
    n -= 1;

    if (n < 0) {
        n = 9999;
    }

    return n;
}

int L(int n) {
    return (n % 1000) * 10 + (n / 1000);
}

int R(int n) {
    return (n % 10) * 1000 + (n / 10);
}

void solution(){
    queue<pair<int, string>> q;

    q.push({ A,"" });
    visit[A] = true;

    while (!q.empty()) {
        int n = q.front().first;
        string s = q.front().second;

        q.pop();

        if (n == B) {
            cout << s << endl;
            break;
        }

        int nn = D(n);
        if (!visit[nn]) {
            visit[nn] = true;
            q.push({ nn,s + 'D' });
        }

        nn = S(n);
        if (!visit[nn]) {
            visit[nn] = true;
            q.push({ nn,s + 'S' });
        }

        nn = L(n);
        if (!visit[nn]) {
            visit[nn] = true;
            q.push({ nn,s + 'L' });
        }

        nn = R(n);
        if (!visit[nn]) {
            visit[nn] = true;
            q.push({ nn,s + 'R' });
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> T;

    while (T--) {
        memset(visit, 0, sizeof(visit));

        cin >> A >> B;

        solution();
    }

    return 0;
}