BOJ - 9019 DSLR

한 수를 다른 수로 변환하는데 걸리는 최소 명령어를 구하는 문제이다.

문제 해결 전략
각 경우마다 bfs를 적용해야 하는데, 처음에는 함수 수행 결과를 각 경우에 따로 해 주었다.

즉, 각 경우마다 while문을 돌릴 때 그 내부에서 함수 적용 후 이미 나왔던 값이면 큐에 푸시를 안하는 방법을 택했었다.

이 방법으로 실행한 결과 자꾸 시간초과가 났다.

생각해보니 숫자는 0~9999까지 고정이고, 각 수마다 함수 적용 결과는 같다.

또한 함수 적용을 매 케이스 마다 할 필요가 없이 미리 다 해둔 후 케이스마다 bfs시에 이미 만들어둔 값을 통해 체크만 하면 됐다.

위와 같이 코드를 수정한 결과 시간초과를 해결할 수 있었다.

코드

#include <iostream>
#include <vector>
#include <string>
#include <queue>

using namespace std;

int D(int n){
    return (n*2)%10000;
}

int S(int n){
    return (n-1+10000)%10000;
}

int L(int n){
    return (n%1000)*10 + n/1000;
}

int R(int n){
    return (n/10) + (n%10)*1000;
}

int main() {
    int n;
    cin >> n;
    vector<pair<int,int>> v;
    vector<string> ans;
    for(int i=0;i<n;i++){
        int s1, s2;
        cin >> s1 >> s2;
        v.push_back(make_pair(s1,s2));
    }

    char func[4] = {'D','S','L','R'};
    int res[10000][4];
    for(int i=0;i<10000;i++){
        res[i][0] = D(i);
        res[i][1] = S(i);
        res[i][2] = L(i);
        res[i][3] = R(i);
    }

    for(int i=0;i<v.size();i++){
        vector<int> visited(10000);
        queue<pair<int, string>> q;
        int a = v[i].first;
        int b = v[i].second;
        q.push(make_pair(a,""));
        visited[a] = 1;
        while(!q.empty()){
            int num = q.front().first;
            string acc = q.front().second;
            q.pop();
            if(num == b){
                ans.push_back(acc);
                break;
            }
            for(int j=0;j<4;j++){
                if(visited[res[num][j]] == 1)
                    continue;
                visited[res[num][j]] = 1;
                q.push(make_pair(res[num][j], acc + func[j]));
            }
        }
    }

    for(int i=0;i<ans.size();i++)
        cout << ans[i] << "\n";
    return 0;
}

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