[백준 / BOJ / GOLD 5] 9019 번 : DSLR

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

9019번: DSLR

문제 접근법

• 입력 값과 명령어를 저장할 queue를 만든다.
• 4가지 명령어를 수행할 때 방문을 체크하기 위하여 bool 값 배열을 준비한다.
• 방문한 적이 없을 때 해당하는 명령어를 실행한다.
• 실행했을 때 숫자값과 명령어를 queue에 넣는다.
• 숫자가 원하던 값과 일치하면 명령어를 출력한다.

아래는 코드입니다.

#include <iostream>
#include <queue>
#include <string>
#include <cstring>
 
using namespace std;
 
bool visit[10001];
 
string Bfs(int a, int b)
{
    queue<pair<int, string>> q;
    q.push(make_pair(a, ""));
 
    while (!q.empty())
    {
        int n = q.front().first;
        string dslr = q.front().second;
        q.pop();
 
        if (n == b)
        {
            return dslr;
        }
 
        int num;
        num = (n * 2) % 10000;
 
        if (!visit[num])
        {
            visit[num] = true;
            q.push(make_pair(num, dslr + "D"));
        }
 
        num = n == 0 ? 9999 : n - 1;
        if (!visit[num])
        {
            visit[num] = true;
            q.push(make_pair(num, dslr + "S"));
        }
 
        num = (n % 1000) * 10 + (n / 1000);
        if (!visit[num])
        {
            visit[num] = true;
            q.push(make_pair(num, dslr + "L"));
        }
 
        num = (n % 10) * 1000 + (n / 10);
        if (!visit[num])
        {
            visit[num] = true;
            q.push(make_pair(num, dslr + "R"));
        }
    }
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    int a;
 
    cin >> a;
 
    for (int i = 0; i < a; i++)
    {
        int b, c;
 
        cin >> b >> c;
        cout << Bfs(b, c) << "\n";
 
        memset(visit, false, sizeof(visit));
    }
 
    return 0;
}