9019번: DSLR

시간초과를 해결하는게 상당히 까다로운 문제다.

string 사용을 최소화하여  BFS로 탐색한다면 정답에 도달할 수 있을 거다.

#include <iostream>
#include <queue>
#include <algorithm>
#include <string>
#include <cstring>
 
int check[10000] = { 0 };
 
int main(void) {
    std::ios_base::sync_with_stdio(0);
    std::cin.tie(0);
    
    int testCase;
    std::cin >> testCase;
 
    int val, reach;
    std::queue<std::pair<std::string, int>> mQ;
    for (int i = 0; i < testCase; i++) {
        std::cin >> val >> reach;
        while (!mQ.empty()) {
            mQ.pop();
        }
        memset(check, false, sizeof(check));
        mQ.push({ "", val });
        int N = 0, value = 0;
        while (!mQ.empty()) {
            N = mQ.front().second;
            std::string total = mQ.front().first;
            mQ.pop();
 
            if (N == reach) {
                std::cout << total << "\n";
                break;
            }
 
            value = 0;
            if (N * 2 >= 10000) { value = (N * 2) % 10000; }
            else { value = N * 2; }
            if (!check[value]) {
                check[value] = 1;
                mQ.push({ total + "D", value });
            }
 
            if (N == 0) { value = 9999; }
            else { value = N - 1; }
            if (!check[value]) {
                check[value] = 1;
                mQ.push({ total + "S", value });
            }
 
            value = (N % 1000) * 10 + (N / 1000);
            if (!check[value]) {
                check[value] = 1;
                mQ.push({ total + "L", value });
            }
 
            value = (N % 10) * 1000 + (N / 10);
            if (!check[value]) {
                check[value] = 1;
                mQ.push({ total + "R", value });
            }
        }
    }
 
    return 0;
}