[알고리즘 문제] 백준 9019번 DSLR

9019번: DSLR (acmicpc.net)

9019번: DSLR

 

문제

 한 수에서 여러 명령을 수행해 다른 값으로 만드는 문제다.

 

아이디어

 만약 문제를 보고 수학 계산으로 해결할 수 있을 거라 생각했다면 함정에 빠진 것이다. 숫자 사이를 공식으로 구할 방법은 없으며, 각 숫자를 그래프의 노드로 보고 DSLR 명령을 노드 사이의 간선으로 생각한다면 BFS를 통해 둘 사이의 거리를 구할 수 있다.

 

 1. 초기 값에서 시작하는 BFS 큐를 만든다.

 2. 현재 위치에서 D, S, L, R을 적용한 숫자를 큐에 넣는다.

 3. 최종 값에 도착하면 탐색을 종료한다.

     숫자가 최대 10000이여서 시간 초과를 걱정하지 않아도 된다.

 4. 경로를 출력하기 위한 데이터는 따로 저장한다.

 

경로는 BFS 큐에 숫자와 함께 넣거나, 외부 배열로 자신의 전 단계를 저장하는 배열을 만들면 된다.

 

코드

// No.9019 DSLR

#include <iostream>
#include <array>
#include <queue>
#include <utility>
#include <cstring>
#include <stack>
using namespace std;

struct dslr {
    array<int, 4> n;

    dslr() = default;

    dslr(int i) {
        n[3] = i % 10;
        i /= 10;
        n[2] = i % 10;
        i /= 10;
        n[1] = i % 10;
        i /= 10;
        n[0] = i % 10;
    }

    int to_num() {
        return n[0] * 1000 + n[1] * 100 + n[2] * 10 + n[3];
    }

    dslr D() {
        int num = this->to_num();
        dslr a = dslr(num * 2 % 10000);
        return a;
    }

    dslr S() {
        int num = this->to_num();
        num -= 1;
        if (num < 0)
            num = 9999;
        return dslr(num);
    }

    dslr L() {
        dslr a;
        a.n[0] = this->n[1];
        a.n[1] = this->n[2];
        a.n[2] = this->n[3];
        a.n[3] = this->n[0];
        return a;
    }

    dslr R() {
        dslr a;
        a.n[0] = this->n[3];
        a.n[1] = this->n[0];
        a.n[2] = this->n[1];
        a.n[3] = this->n[2];
        return a;
    }
};

int T;
queue<dslr> q;
int check[10000];
int target, here;
char pre_inst[10000];
int pre_num[10000];

void BFS() {
    while (!q.empty()) {
        dslr next = q.front(); q.pop();

        if (next.to_num() == target) {
            return;
        }

        if (check[next.D().to_num()] == 0) {
            pre_inst[next.D().to_num()] = 'D';
            pre_num[next.D().to_num()] = next.to_num();
            check[next.D().to_num()] = 1;
            q.push(next.D());
        }
        if (check[next.S().to_num()] == 0) {
            pre_inst[next.S().to_num()] = 'S';
            pre_num[next.S().to_num()] = next.to_num();
            check[next.S().to_num()] = 1;
            q.push(next.S());
        }
        if (check[next.L().to_num()] == 0) {
            pre_inst[next.L().to_num()] = 'L';
            pre_num[next.L().to_num()] = next.to_num();
            check[next.L().to_num()] = 1;
            q.push(next.L());
        }
        if (check[next.R().to_num()] == 0) {
            pre_inst[next.R().to_num()] = 'R';
            pre_num[next.R().to_num()] = next.to_num();
            check[next.R().to_num()] = 1;
            q.push(next.R());
        }
     }
}

int main(void) {
    cin >> T;
    for (int i = 0; i < T; i++) {
        cin >> here >> target;
        q.push(dslr(here));
        BFS();

        stack<char> inst;
        int num = target;
        while (num != here) {
            inst.push(pre_inst[num]);
            num = pre_num[num];
        }
        while (!inst.empty()) {
            cout << inst.top();
            inst.pop();
        }
        cout << '\n';

        memset(check, 0, sizeof(check));
        memset(pre_inst, 0, sizeof(pre_inst));
        memset(pre_num, 0, sizeof(pre_num));
        q = queue<dslr>();
    }
}

 

기타

 코드에 dslr 숫자를 객체로 만들어 관리하려 했지만, 오히려 코드가 복잡해지는 문제가 생겼다. 알고리즘 문제를 풀 때 객체를 만드는 건 최대한 지양해야 할 것이다..