[백준] 9019번 DSLR

문제

---

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

풀이과정

---

소수 경로 문제와 어떻게 보면 비슷한 문제지만 정말 까다로운 문제였다. 강의를 들으며 대충의 풀이방법을 알고 구현을 시작했지만 시간이 꽤 걸렸다.

BFS문제며 최소횟수 문제이기 때문에 dist[]로 횟수를 저장한다. 하지만 이 문제는 어떤 연산을 통해서 수를 만들었나 출력해야하기 때문에 연산의 방법도 저장해야한다.
또한, 연산 전의 숫자를 저장해야한다.

소스코드

---

#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <queue>

using namespace std;

#define MAX 10001

bool visited[MAX];
int dist[MAX];
int from[MAX];
char how[MAX];
char cmd[4] = { 'D','S','L','R' };

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

    int T;
    cin >> T;

    for (int test_case = 0; test_case < T; test_case++)
    {
        int a, b;
        cin >> a >> b;

        queue<int> q;
        q.push(a);
        visited[a] = true;
        dist[a] = 0;

        while (!q.empty())
        {
            int now = q.front(); q.pop();

            for (int i = 0; i < 4; i++)
            {
                if (cmd[i] == 'D')
                {
                    int next = (now * 2) % 10000;
                    if (visited[next] == false)
                    {
                        q.push(next);
                        visited[next] = true;
                        dist[next] = dist[now] + 1;
                        from[next] = now;
                        how[next] = cmd[i];
                    }
                }
                else if (cmd[i] == 'S')
                {
                    int next = now == 0 ? 9999 : now - 1;
                    if (visited[next] == false)
                    {
                        q.push(next);
                        visited[next] = true;
                        dist[next] = dist[now] + 1;
                        from[next] = now;
                        how[next] = cmd[i];
                    }
                }
                else if (cmd[i] == 'L')
                {
                    int next = (now % 1000) * 10 + now / 1000;
                    if (visited[next] == false)
                    {
                        q.push(next);
                        visited[next] = true;
                        dist[next] = dist[now] + 1;
                        from[next] = now;
                        how[next] = cmd[i];
                    }
                }
                else if (cmd[i] == 'R')
                {
                    int next = (now / 10) + (now % 10) * 1000;
                    if (visited[next] == false)
                    {
                        q.push(next);
                        visited[next] = true;
                        dist[next] = dist[now] + 1;
                        from[next] = now;
                        how[next] = cmd[i];
                    }
                }
            }
        }

        string ans = "";

        while (a != b)
        {
            ans += how[b];
            b = from[b];
        }

        // <algorithm> 필요
        reverse(ans.begin(), ans.end());

        cout << ans << "\n";

        // memset의 헤더는 <cstring>
        memset(dist, 0, sizeof(dist));
        memset(visited, false, sizeof(visited));
        memset(how, 0, sizeof(how));
        memset(from, 0, sizeof(from));
    }    

    return 0;
}