9019 DSLR

www.acmicpc.net/problem/9019

9019번: DSLR

 

BFS 문제인가? 한번 생각하게 하는 문제.

언제 우리가 원하는 수를 만들 지 모르니 D, S, L, R 모든 연산을 해보고, 이미 한번 만났던 애들인지 한번 체크해보고 다음을 계산하게하여 푸는 문제.

 

Queue에 연산결과(수)와 지금까지의 연산과정을 모두 넣어야하므로 std::queue<pair<int, string>> 으로 진행하였다.

 

이 문제에서 키 포인트

1. 이미 연산했던 수 인지 아닌지 체크하기. -> 이미 연산했던 수라면 다음 연산을 할 필요가 없음.

2. D, S, L, R 연산 실수하지 않기.

3. queue에 연산결과와 연산과정을 모두 넣기.

 

 

#include <bits/stdc++.h>
using namespace std;
#define swap(a,b) (a)^=(b)^=(a)^=(b)
#define endl '\n'
typedef long long lld;
 
int main()
{
    ios_base::sync_with_stdio(NULL);
    cin.tie(NULL);
    cout.tie(NULL);
    int tc;
    cin >> tc;
    while(tc--)
    {
        vector<bool> check(10000, false);
        int a, b;
        cin >> a >> b;
        check[a] = true;
        queue<pair<int, string>> q;
        q.push({a, ""});
        while(!q.empty())
        {
            int tmp = q.front().first;
            string ans = q.front().second;
            q.pop();
            if(tmp == b)
            {
                cout << ans << endl;
                break;
            }
            int d, s, l, r;
            d = tmp*2>9999?tmp*2-10000:tmp*2;
            s = tmp-1>=0?tmp-1:tmp-1+10000;
            l = ((tmp%1000)*10) + (tmp/1000);
            r = (tmp/10) + (tmp%10)*1000;
            if(!check[d])
            {
                q.push({d, ans+"D"});
                check[d] = true;
            }
            if(!check[s])
            {
                q.push({s, ans+"S"});
                check[s] = true;
            }
            if(!check[l])
            {
                q.push({l, ans+"L"});
                check[l] = true;
            }
            if(!check[r])
            {
                q.push({r, ans+"R"});
                check[r] = true;
            }
        }
    }
    return 0;
}