[알고리즘 문제] 백준9019 - DSLR

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

9019번: DSLR

 

문제에서 두개의 정수(n1,n2)를 주고, 정수(n1)를 조작할 수 있는 4개의 명령어(D,S,L,R)이 나온다. 이 명령어를 사용하여 n1을 n2로 변환하는데 최소명령어를 출력하면 됩니다.

 

아이디어는 bfs를 사용하였습니다. 그리고 최소값을 구해야 하기 때문에 visited[]를 사용하여 한번 사용한 숫자는 다시 사용하지 않도록 합니다. 왜냐하면 처음 사용한 경우의 수가 최소를 의미하기 때문에 두번째 사용할 때 부터는 해당 숫자는 최소의 기준을 벗어나기 때문에 의미가 없어집니다.

 

#include <iostream>
#include <queue>

using namespace std;

int main()
{

    int t;
    cin >> t;

    while (t--)
    {

        int n1, n2;
        cin >> n1 >> n2;

        queue<pair<int, string>> que;
        que.push(make_pair(n1, ""));

        bool visited[10000] = {0};
        visited[n1] = true;

        while (!que.empty())
        {
            int num = que.front().first;
            string str = que.front().second;
            que.pop();

            if (num == n2)
            {
                cout << str << "\n";
                break;
            }

            int newNum;

            // D
            newNum = (2 * num) % 10000;
            if (!visited[newNum])
            {
                que.push(make_pair(newNum, str + "D"));
                visited[newNum] = true;
            }

            // S
            newNum = (num - 1) < 0 ? 9999 : num - 1;
            if (!visited[newNum])
            {
                que.push(make_pair(newNum, str + "S"));
                visited[newNum] = true;
            }

            // L
            newNum = (num % 1000 / 100) * 1000 + (num % 1000 % 100 / 10) * 100 + (num % 10) * 10 + (num / 1000);
            if (!visited[newNum])
            {
                que.push(make_pair(newNum, str + "L"));
                visited[newNum] = true;
            }

            newNum = (num % 10) * 1000 + (num / 1000) * 100 + (num % 1000 / 100) * 10 + (num % 1000 % 100 / 10);
            if (!visited[newNum])
            {
                que.push(make_pair(newNum, str + "R"));
                visited[newNum] = true;
            }
        }
    }
    return 0;
}