[ 백준 / C++ ] 9019 : DSLR

[ 문제 ]

 

9019번: DSLR (acmicpc.net)

 

[ 접근방법 ]

 

BFS를 활용한다.

시간복잡도는 O(T * N)으로 충분하다.

 

[ 소스코드 ]

 

#include <iostream>
#include <queue>

using namespace std;

struct node
{
    int n;
    string cmd;
};

int t, a, b;
bool chk[10000];
queue<node> que;

int D(int x)
{
    return (2 * x) % 10000;
}

int S(int x)
{
    return x ? x - 1 : 9999;
}

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

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

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

    cin >> t;
    while (t--)
    {
        cin >> a >> b;
        for (int i = 0; i < 10000; i++)
            chk[i] = false;
        while (!que.empty())
            que.pop();
        que.push({a, ""});
        chk[a] = true;

        while (!que.empty())
        {
            node qf = que.front();
            que.pop();
            if (qf.n == b)
            {
                cout << qf.cmd << "\n";
                break;
            }
            if (!chk[D(qf.n)])
            {
                que.push({D(qf.n), qf.cmd + 'D'});
                chk[D(qf.n)] = true;
            }
            if (!chk[S(qf.n)])
            {
                que.push({S(qf.n), qf.cmd + 'S'});
                chk[S(qf.n)] = true;
            }
            if (!chk[L(qf.n)])
            {
                que.push({L(qf.n), qf.cmd + 'L'});
                chk[L(qf.n)] = true;
            }
            if (!chk[R(qf.n)])
            {
                que.push({R(qf.n), qf.cmd + 'R'});
                chk[R(qf.n)] = true;
            }
        }
    }

    return 0;
}