[백준] 9019: DSLR (C++)

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

문제

---

원문에 나오는 D, S, L, R 연산을 구현하여 A, B입력 시 A→B가 될 때 까지 어떤 연산을 해야하는 지 출력해야 하는 문제이다.

아이디어

---

BFS를 통해 D, S, L, R, DD, DS, DL, DR, SD, SS, SL, SR, ...처럼 레벨 단위로 숫자를 확인한다.

 

여기까진 OK. 하지만 문자열의 제한이 없기 때문에 DSLDLSDRRSRSDSL... 같이 긴 숫자는 Queue에 메모리초과가 발생한다.

숫자는 0~10000미만이다. 이것을 활용하여 10000까지 visit을 확인하여 이미 확인한 숫자는 확인하지 않는다.

 

또한 자료형에 대해서도 short로 바꿔줄 수 있다. int를 쓰면 틀리는 지는 확인해보지 않았지만 일단 short를 써도 괜찮은 것을 알고 있으니 사용한다.

Code

---

#include <iostream>
#include <queue>

using namespace std;

void init() {
    cin.tie(NULL);
    cout.tie(NULL);
    ios::sync_with_stdio(false);
}

short D_(short n) { return (n * 2) % 10000; }
short S_(short n) { return n == 0 ? 9999 : n - 1; }
short L_(short n) {
    unsigned short d1, d2, d3, d4;
    d1 = n / 1000;
    d2 = (n / 100) % 10;
    d3 = (n / 10) % 10;
    d4 = n % 10;
    return d2 * 1000 + d3 * 100 + d4 * 10 + d1;
}
short R_(short n) {
    unsigned short d1, d2, d3, d4;
    d1 = n / 1000;
    d2 = (n / 100) % 10;
    d3 = (n / 10) % 10;
    d4 = n % 10;
    return d4 * 1000 + d1 * 100 + d2 * 10 + d3;
}
short (*f[4])(short) = {D_, S_, L_, R_};
const string pu5h[] = {"D", "S", "L", "R"};

void bfs(short A, short B) {
    bool visited[10000] = {false};
    queue<pair<int, string>> q;
    q.push({A, ""});
    visited[A] = true;

    while (!q.empty()) {
        short A = q.front().first;
        string pou = q.front().second;
        q.pop();
        if (A == B) {
            cout << pou << endl;
            return;
        }
        for (short i = 0; i < 4; i++) {
            short next_A = f[i](A);
            if (!visited[next_A]) {
                visited[next_A] = true;
                q.push({next_A, pou + pu5h[i]});
            }
        }
    }
}

int main() {
    init();
    short T;
    cin >> T;
    while (T--) {
        short A, B;
        cin >> A >> B;
        bfs(A, B);
    }
    return 0;
}

코드 짜면서 약간 함수 포인터를 복기하며 짜봤는데 그런 코드적인 감각에 취해버렸다.