[ 백준 9019 ] DSLR (C++)

백준의 DSLR(9019) 문제이다.

( 문제 바로가기 )

[ 문제풀이 ]

1. 문제는 기본적인 BFS로 풀리는 문제이다.

   본인은 Queue에 (현재 숫자, 연산법) 을 쌍으로 넣어서 관리하였다.

   현재 숫자는 int형으로, 연산법은 string형으로 관리하였고, 이미 방문한 값에 대해서는 다시 재탐색 하지 않도록

   구현하였다.

[ 소스코드 ]

#include<iostream>
#include<cstring>
#include<string>
#include<queue>
 
#define endl "\n"
#define MAX 10000
using namespace std;
 
int Start, End;
bool Visit[MAX];
 
void Initialize()
{
    memset(Visit, false, sizeof(Visit));
}
 
void Input()
{
    cin >> Start >> End;
}
 
string BFS(int a)
{
    queue<pair<int, string>> Q;
    Q.push(make_pair(a, ""));
    Visit[a] = true;
 
    while (Q.empty() == 0)
    {
        int x = Q.front().first;
        string s = Q.front().second;
        Q.pop();
 
        if (x == End) return s;
        
        int nx = x * 2;
        if (nx > 9999) nx = nx % 10000;
        if (Visit[nx] == false)
        {
            Visit[nx] = true;
            Q.push(make_pair(nx, s + "D"));
        }
 
        nx = x - 1;
        if (nx < 0) nx = 9999;
        if (Visit[nx] == false)
        {
            Visit[nx] = true;
            Q.push(make_pair(nx, s + "S"));
        }
 
        nx = (x % 1000) * 10 + (x / 1000);
        if (Visit[nx] == false)
        {
            Visit[nx] = true;
            Q.push(make_pair(nx, s + "L"));
        }
 
        nx = (x % 10) * 1000 + (x / 10);
        if (Visit[nx] == false)
        {
            Visit[nx] = true;
            Q.push(make_pair(nx, s + "R"));
        }
    }
}
 
 
void Solution()
{
    string R = BFS(Start);
    cout << R << endl;
}
 
void Solve()
{
    int Tc;
    cin >> Tc;
    for (int T = 1; T <= Tc; T++)
    {
        Initialize();
        Input();
        Solution();
    }
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}