[백준 9019] DSLR

🔗알고리즘 문제

시간초과로 인해 꽤나 고생했던 문제, BFS를 이렇게도 활용할 수 있구나라는 생각이 드는 문제였다.

문제 분석

이 문제는 A가 B가 될때 까지 사용되는 커맨드를 알아내는 문제이다.

D: n에 2를 곱한 후 10000으로 나눈 나머지 값
S: n에서 1을 뺀 값, 만약 0보다 작아진다면 9999
L: n의 각 자릿수를 왼쪽으로 회전
R: n의 각 자릿수를 오른쪽으로 회전

이 때 사용되는 커맨드는 위에 4개와 같다.

발상

이 문제는 현재 넘버에서 4가지의 커멘드를 사용하여 다음 값을 찾아내고 커멘드를 더해주는 식으로 구현할 수 있는 문제이다. 따라서 그래프 탐색 문제라고 판단하였다.

int L(int origin){
    int temp = origin;
    int ten = pow(10, digit(origin));

    temp /= ten;

    return (origin - temp * ten) + temp;
}

int R(int origin){
    int d = digit(origin);

    int temp = origin % 10;
    origin /= 10;

    return origin + temp * pow(10, d);
}

내가 처음에 구현한 L과 R의 값을 구하는 함수이다. L함수를 예시로 들면 오른쪽 값을 왼쪽으로 보내기 위하여 origin의 자릿수를 구해 origin의 오른쪽 값을 담는 temp변수를 만들어 origin에 더한 후 origin의 오른쪽 값을 빼주었다.

하지만 여기서 내가 잘못 생각한 부분은 n은 항상 d1 d2 d3 d4 4자리로 이루어져 있다는 것이다.

n = 123 ( 0 1 2 3 )

L연산 -> 1230
R연산 -> 3012

해당 부분을 만족하도록 수식을 수정하여 문제를 해결하였다.

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

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

알고리즘 설계

1. a와 b의 값을 입력받는다.
2. a값을 시작으로 D, S, L, R 연산을 시작한다.
3. 연산 후의 값이 아직 탐색하지않은 값이라면 현재까지의 커맨드에 해당 커맨드를 더해 저장하여준다.
4. b에 도착할 때까지 반복한다.

코드

#include<iostream>
#include<queue>

using namespace std;

int D(int origin);
int S(int origin);
int L(int origin);
int R(int origin);

void check_num(int next, queue<pair<int, string>> &q, bool* check, string cmd){
    if(check[next] == true)
        return;

    check[next] = true;
    q.push({ next, cmd });
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    int t;

    cin >> t;

    while(t--){
        int a;
        int b;

        bool check[10001] = {};

        cin >> a >> b;

        queue<pair<int, string>> q;
        q.push({ a, "" });
        check[a] = true;

        while(!q.empty()){
            pair<int, string> node = q.front();
            q.pop();

            if(node.first == b){
                cout << node.second << "\n";
                break;
            }

            check_num(D(node.first), q, check, node.second + "D");
            check_num(S(node.first), q, check, node.second + "S");
            check_num(L(node.first), q, check, node.second + "L");
            check_num(R(node.first), q, check, node.second + "R");
        }
    }
}

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

int S(int origin){
    return (origin - 1 >= 0 ? origin - 1 : 9999);
}

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

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