백준 9019 DSLR

문제링크 : https://www.acmicpc.net/problem/9019

아이디어

• BFS를 사용해서 최소 시간을 구하자

  • 각 숫자에 대해 각각 연산한 뒤 값이 맞으면 출력
  • 값이 다르면 큐에 넣고 계속 수행
  • 이때 연산한 값을 가지고 있기 위해서, q에 과거 수행한 연산도 같이 등록

• 주의해야할 것

  • L과 R 연산에서 4자리를 맞추기 위해 0을 채운 뒤 연산 수행
  • 그리고 반환할때는 앞의 0을 없애기

시간복잡도 계산

• BFS연산 최대 1e4번
• D, S 연산 : O(1)
• L, R 연산 : O(1)

인트 계산

• q<pair<int, string>> : 숫차 최대값이 1e4로 정해져 있어서 괜찮음

코드(C++)

#include <iostream>
#include <queue>
#include <string>
 
using namespace std;
 
 
bool chk[10010];
int main() {
 
    int T; cin >> T;
    while(T--) {
        // 메모리 초기화
        fill(chk, chk+10010, 0);
        
        int N,M; cin >> N >> M;
        queue<pair<int, string>> q;
        q.push(make_pair(N, ""));
        chk[N] = 1;
        while(!q.empty()) {
            auto eq = q.front(); q.pop();
            int en = eq.first;
            string cal = eq.second;
            
            // 비교
            if(en == M) {
                cout << cal << '\n';
                break;
            }
            
            int calD =en*2%10000;
            if(chk[calD] == 0) {
                q.push(make_pair(calD, cal+"D"));
                chk[calD] = 1;
            }
            
            int calS = en-1;
            if(calS == -1) calS = 9999;
            if(chk[calS] == 0) {
                q.push(make_pair(calS, cal+"S"));
                chk[calS] = 1;
            }
            
            int cl = en%1000 * 10 + en/1000;
            if(chk[cl] == 0) {
                q.push(make_pair(cl, cal+"L"));
                chk[cl] = 1;
            }
            
            int cr = en%10 * 1000 + en/10;
            if(chk[cr] == 0) {
                q.push(make_pair(cr, cal+"R"));
                chk[cr] = 1;
            }
        }
    }
    
    return 0;
}
 

문제유형

• BFS - 최소 거리 구하기

비슷한 문제

• https://www.acmicpc.net/problem/14226
• https://www.acmicpc.net/problem/1963
• https://www.acmicpc.net/problem/1107
• https://www.acmicpc.net/problem/9019