[C++] 백준 9019번 DSLR

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

9019번: DSLR

풀이

구현(Implementation)과 관련된 문제이다. 처음엔, 큐와 덱을 사용해서 해결하려 했으나 메모리초과가 뜬다. 그래서 그냥 Resister 구조체를 만들어서 해결했다. 사실 자릿수가 4자리뿐이라 이게 훨씬 쉬운 방법이었다.

1. Resister 구조체는 각 자리수 d1~d4 저장 변수, 원래 숫자 저장을 위한 변수 num, 커맨드 저장 변수 cmd와 DSLR함수, 변수 업데이트용 save 함수를 가진다.

2. D: 문제에서 주어진 대로 구현한다. 마지막에 d1~d4를 업데이트 하기 위해 save 함수를 콜한다.

3. S, L, R 또한 마찬가지 이다. L 과 R 함수는 4자리 뿐이니 하드코딩하자...ㅎ 굳이 덱을 쓰는것보다 빠르다.

4. 최단 거리 문제이기 때문에 BFS를 돌려서 해결하면 된다.

 

리뷰

1. r 변수 커맨드를 업데이트 할 때, if문 밖에서 할 경우 시간 초과가 뜬다. 

2. 체크가 끝난 후에 업데이트 하도록 하자.

3. 구조체를 만들어서 사용하는게 STL 자료구조 사용하는 것보다 쉬울 수 있다. 단순하게 생각해서 쉽게 쉽게 가자.

#include <iostream>
#include <queue>
#include <string>
#include <cstring>

using namespace std;

int T, B, A;
bool visited[10000];

struct Resister{
    int d1, d2, d3, d4;
    int num;
    string cmd="";
    Resister(int a){
        save(a);
    }
    void save(int a){
        num = a;
        d4=a%10;
        a/=10;
        d3=a%10;
        a/=10;
        d2=a%10;
        a/=10;
        d1=a%10;
    }

    void D(){
        if (num*2 > 9999) { num = (num*2)%10000; } 
        else { num*=2; }
        save(num);
    }

    void S(){
        if (num==0) { num=9999; }
        else { num-=1; }
        save(num);
    }

    void L(){
        int n=d1;
        d1=d2;
        d2=d3;
        d3=d4;
        d4=n;
        num = d1*1000+d2*100+d3*10+d4;
    }
    void R(){
        int n=d4;
        d4=d3;
        d3=d2;
        d2=d1;
        d1=n;
        num = d1*1000+d2*100+d3*10+d4;
    }
};

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    // freopen("input.txt", "r", stdin);
    cin >> T;
    for (int i=0; i<T; i++){
        cin >> A >> B;

        queue<Resister> q;
        q.push(Resister(A));
        memset(visited, 0, sizeof(visited));
        visited[A] = 1;

        while (!q.empty()){
            Resister v = q.front();
            q.pop();

            if (v.num == B){
                cout << v.cmd << "\n";
                break;
            }
            
            // D
            Resister r(v.num);
            r.D();
            if (!visited[r.num]){
                visited[r.num]=1;
                r.cmd = v.cmd+'D';
                q.push(r);
            }
            // S
            r.save(v.num);
            r.S();
            if (!visited[r.num]){
                visited[r.num]=1;
                r.cmd = v.cmd+'S';
                q.push(r);
            }
            // L
            r.save(v.num);
            r.L();
            if (!visited[r.num]){
                visited[r.num]=1;
                r.cmd = v.cmd+'L';
                q.push(r);
            }
            // R
            r.save(v.num);
            r.R();
            if (!visited[r.num]){
                visited[r.num]=1;
                r.cmd = v.cmd+'R';
                q.push(r);
            }
        }
    }
    return 0;
}