백준, BOJ, 9019번, DSLR : C++ [CPP]

이런 문제를 싫어하지만..

자주 나오는듯 하다.

내용이 많아서 어려운 문제다.

 

게다가 6초나 준다..

시간이 얼마나 많이 걸릴 지 예상이 가는 문제다.

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

 

---

 

#맞은 풀이

#include <bits/stdc++.h>

using namespace std;

const int MAX = 10000;

int A,B;

bool visited[MAX];

int main(){
    int T;
    cin >> T;
    //테케
    while(T--){
        cin >> A >> B;
        
        //초기화
        for(int i = 0; i<10000; i++)
            visited[i] = false;
            
            
        queue<pair<int, string>> q;
        
        q.push({A, ""});
        visited[A] = true;
        
        while(!q.empty()){
            auto cur = q.front();
            q.pop();
            
            int curNum = cur.first;
            
            //해당 상태라면
            if(curNum == B){
                cout << cur.second << '\n';
                break;
            }
            
            //4가지 경우 다 탐색해봄 (방문했다면 이미 최단경로 존재하므로 탐색 x)
            int next;
            //D
            next = (curNum * 2)%MAX;
            if(!visited[next]){
                q.push({next, cur.second + "D"});
                visited[next] = true;
            }
            //S
            next = (curNum - 1) < 0 ? 9999 : curNum - 1;
            if(!visited[next]){
                q.push({next, cur.second + "S"});
                visited[next] = true;
            }
            //L
            next = (curNum%1000)*10 + (curNum/1000);
            if(!visited[next]){
                q.push({next, cur.second + "L"});
                visited[next] = true;
            }
            //R
            next = (curNum/10) + (1000*(curNum%10));
            if(!visited[next]){
                q.push({next, cur.second + "R"});
                visited[next] = true;
            }
        }
        
    }
    return 0;
}

 

내용이 많아 어렵고 BFS인가?? 싶은 문제일 것이다.