DSLR 9019번 [백준]

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

9019번: DSLR

 

BFS을 활용하여 풀수있는 간단한 문제입니다. visited배열을 사용해서 한번 접근한 숫자에는 다시 접근하지 못하도록 하여 메모리 초과를 방지해야 합니다.

 

지역변수의 초기값은 쓰레기값으로 초기화 된다는 것을 깜빡하고 있어서 푸는데에 오래 걸렸습니다.

#include<bits/stdc++.h>
#include<sys/types.h>

using namespace std;
#define endl '\n'
#define fast_io ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define rep(i, j) for(ll i=0;i<j;i++)
#define ff first
#define ss second

bool visited[10000];

void solve() {
    int a, b;
    cin >> a >> b;
    queue<pair<string, int>> q;
    q.push({"", a});
    string result;
    bool visited[10000] ={false,};
    visited[a] = true;
    while (!q.empty()) {

        string s = q.front().ff;
        int num = q.front().ss;
        q.pop();

        if (num == b) {
            cout << s << endl;
            return;
        }

        int ans[4];
        ans[0] = (num * 2) % 10000;
        ans[1] = (num <= 0) ? 9999 : num - 1;
        ans[2] = ((num % 1000) * 10) + (num / 1000);
        ans[3] = ((num % 10) * 1000) + (num / 10);
        string str[] = {"D", "S", "L", "R"};

        rep(i, 4) {
            if (!visited[ans[i]]) {
                visited[ans[i]] = true;
                q.push({s + str[i], ans[i]});
            }
        }
    }
}

int main() {
    fast_io;

    int t;
    cin >> t;
    rep(i, t)solve();
    return 0;
}