백준 9019 DSLR(c++)

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

9019번: DSLR

이 문제는 BFS라고 볼 수 있습니다. 시작 값과 끝 값을 두고 D(num*2 % 10000), S( s-1 > 0 ? 9999 : s-1), L(자리수 왼쪽 한 칸 이동), R(자리 수 오른쪽으로 한 칸 이동) 연산을 하는데, 시작 값에서 끝 값을 만들기 위한 연산의 최솟값을 구하는 문제입니다.

 

3
1234 3412
1000 1
1 16

테스트케이스를 예시로 들면, 1234에서 3412을 만들기 위해서는 1234 -> 2341(L) -> 3412(L) 총 L 연산이 두 번 필요하고,

1000에서 1을 만들기 위해서는 왼쪽으로 한 칸 이동하면, 0001이 되는데, 앞자리 0은 없는 수나 다름없기에 1을 담아 줍니다.

1에서 16을 만들기 위해서는 2^4인 DDDD가 필요하게 됩니다. 연산 횟수를 누적시켜 주면서 만들어야 하는 값을 찾아가는 BFS 탐색으로 풀 수 있었습니다.

방문 횟수 같은 경우는 첫번째 연산 1234 -> 4312을 만들고 다음 경우를 조사해야 하기 때문에 BFS탐색을 하기 전 -1로 초기화 해주었습니다.

<코드>

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

bool check[10001];
int start, End;
using namespace std;

void bfs()
{
    queue<pair<int, string>> q;
    q.push(make_pair(start, ""));
    check[start] = true;
    while (!q.empty())
    {
        int x = q.front().first;
        string result = q.front().second;
        q.pop();
        if (x == End)
        {
            cout << result << '\n';
            return;
        }

        int d = (x * 2) % 10000;
        if (!check[d])
        {
            check[d] = true;
            q.push(make_pair(d, result + "D"));
        }

        int s = x - 1 < 0 ? 9999 : x - 1;
        if (!check[s])
        {
            check[s] = true;
            q.push(make_pair(s, result + "S"));
        }

        int l = (x % 1000) * 10 + (x / 1000); // ex) 1234 -> 2341
        if (!check[l])
        {
            check[l] = true;
            q.push(make_pair(l, result + "L"));
        }

        int r = (x % 10) * 1000 + (x / 10); // ex) 1234 -> 4123
        if (!check[r])
        {
            check[r] = true;
            q.push(make_pair(r, result + "R"));
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int t;
    cin >> t;
    while (t--)
    {
        cin >> start >> End;
        memset(check, false, sizeof(check));
        bfs();
    }
    return 0;
}