백준 9019번: DSLR (C++)

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

문제를 잘못 이해해서 시간을 많이 낭비한 문제이다.

레지스터에 저장될 수 있는 수인 n은, 10000 미만, 0 이상의 수가 맞기는 한데, 무조건 네 자리로 이루어져 있다.

즉 123 이라고 하더라도, 그냥 123이 아니라 _123이라는 것이다. 123에 L연산을 하면 231이 되지만, _123에 L연산을 해봐야

123_ 이고, 결국 123이다.

본인처럼 잘못 이해하고 풀게 되면 시간초과에 걸리게 된다. 틀렸습니다가 아니라 시간 초과라서, 로직이 잘못되었다는 걸 아는데까지 시간이 오래 걸렸다.

마지막에, 최적의 결과를 내기 위한 연산의 흐름을 출력해야 하기 때문에, 큐에 삽입될 때마다 이전 노드와 사용된 연산을 parent 배열에 저장해준다.

parent[다음 수] = {이전 수, 사용된 연산} 이렇게 된다.

마지막에는 결국 parent[목표 수] 부터 시작해서 거꾸로 타고 올라가면서 처음 수가 나올 때까지 사용된 연산을 거꾸로 출력해주면 된다.

#pragma warning(disable :4996)
#include<iostream>
#include<queue>
#include<string>
#include<vector>
using namespace std;
 
int T, src, dst;
char cmd[4] = { 'D', 'S', 'L','R' };
pair<int, char> parent[10000];
 
bool vis[10000];//초기화 필요
queue<int> q;
void bfs() {
    vis[src] = true;
    q.push(src);
 
    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        //cout << cur << '\n';
        if (cur == dst) return;
 
        for (int i = 0; i < 4; i++) {
            int next;
            if (cmd[i] == 'D') {
                next = 2 * cur;
                if (next > 9999) next %= 10000;
            }
            else if (cmd[i] == 'S') {
                next = cur - 1;
                if (cur == 0) next = 9999;
            }
            else if (cmd[i] == 'L') 
                next = (cur % 1000) * 10 + cur / 1000;
            
            else if (cmd[i] == 'R') 
                next = (cur % 10) * 1000 + cur / 10;
            
            if (vis[next] || next > 10000) continue;
            q.push(next);
            vis[next] = true;
            parent[next] = { cur, cmd[i] }; //next로 숫자가 변할 때 사용된 명령
        }
    }
}
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> T;
    while (T--) {
        cin >> src >> dst;
        bfs();
 
        pair<int, char> prev;
        prev = parent[dst];
        vector<char> v;
        v.push_back(prev.second);
 
        while (1) {
            //cout << prev.first << '\n';
            if (prev.first == src) break;
            prev = parent[prev.first];
            v.push_back(prev.second);
        }
        for (int i = v.size() - 1; i >= 0; i--)
            cout << v[i];
        cout << '\n';
 
        v.clear();
        for (int i = 0; i < 10000; i++)
            vis[i] = false;
        while (!q.empty()) q.pop();
    }
 
    return 0;
}