백준 9019 (DSLR) C++

문제

9019번: DSLR

숫자 a, b를 입력받고 4가지 연산 D, S, L, R을 통해 a가 b로 되게하는 연산을 모두 구하는 문제입니다.

D연산은 a에 2를 곱하고 10000으로 나눕니다.

S연산은  a에 1을 뺀 연산입니다. 만약 음수가 되면 9999가 됩니다.

L연산은 각자릿수를 왼쪽으로 이동시키는 연산입니다. 예를 들어 1234는 2341이 됩니다.

R연산은 각자릿수를 오른쪽으로 이동시키는 연산입니다. 예를 들어 4321은 1432가 됩니다.

 

모든 경우의 수를 살펴보아야 하기 때문에 bruteforce를 이용해 재귀함수를 사용하여 구현하려 했지만

DSLR연산을 정답에 맞는 연산만을 구해야하는데 이를 할 수 없었습니다. 

인터넷에 도움을 찾으니 bfs를 통해 구현하였습니다.

bfs는 tree 형태만을 위해 사용되는줄 알았지만 이렇게 모든 경우의 수를 찾아볼 때에도 구현이 가능한지

몰랐습니다.

queue<pair<int, string>>q;
memset(visit, false, sizeof(visit));

int a, b;
cin >> a >> b;
visit[a] = true;
q.push({ a ,"" });

visit을 통해 DSLR을 통해 만들어진 숫자에 true표시를 할 것입니다.

문제를 보고 어떻게 접근하는지 알기만 해도 쉽게 풀리는 문제였습니다. 

bfs를 찾을 수 있게 노력하겠습니다.

---

전체 코드입니다.

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <cmath>
#include <map>
#include <set>
#include <tuple>
#define MAX 2100000000
#define inf LONG_MAX
#define big(a, b) a > b ? a : b
using namespace std;
using ll = long long;
using ull = unsigned long long;
int a, b;
bool visit[10000];
int main() {
    ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
    int t;
    cin >> t;
    while (t--) {
        queue<pair<int, string>>q;
        memset(visit, false, sizeof(visit));
        int a, b;
        cin >> a >> b;
        visit[a] = true;
        q.push({ a ,"" });
        while (!q.empty()) {
            int key = q.front().first;
            string st = q.front().second;
            q.pop();
 
            if (key == b) {
                cout << st << '\n';
                break;
            }
            int d, s, l, r;
            d = (key * 2) % 10000;
            if (!visit[d]) {
                visit[d] = true;
                q.push({ d, st + "D" });
            }
 
            s = key - 1 < 0 ? 9999 : key - 1;
            if (!visit[s]) {
                visit[s] = true;
                q.push({ s, st + "S" });
            }
 
            l = (key % 1000) * 10 + (key / 1000);
            if (!visit[l]) {
                visit[l] = true;
                q.push({ l,st + "L" });
            }
 
            r = (key / 10) + (key % 10) * 1000;
            if (!visit[r]) {
                visit[r] = true;
                q.push({ r, st + "R" });
            }
        }
    }
    
 
    return 0;
}