[백준] 9019번

이번에는 나름의 최적화 하는 방법을 알게 된 것 같다.

처음에는 구조체를 만들어서 command를 하나씩 기록하게 해서 메모리가 낭비가 많이 됐다.

 

글을 읽어보니 0~9999 사이의 값 밖에 나올 수 없기 때문에 메모리를 그만큼 사용해서 camefrom만 기록하면 메모리를 더욱 효과적으로 관리할 수 있다는 것을 깨달았다.

 

머리 속으로는 bfs로 하면 되겠다. 라고 생각하고 직접 구현해 보니, 역시 시간복잡도 및 여러 경우를 고려해서 개발해야 좋은 결과물이 나온 다는 것을 느꼈다.

 

참고로 막힐 때 마다 claude에게 조언을 들어서 해결한 부분 이 배열로 쪼개는 부분이었다.

#include <algorithm>
#include <cstring>
#include <iostream>
#include <queue>


std::queue<int> q;
bool visited[10000];
int parent[10000];
char cmd[10000];


void queueController(int, const int&);
void rotationR(const int &);
void rotationL(const int &);
void mutlipleDouble(const int &);
void decreaseOne(const int &);


int main() {
    int t;
    std::cin >> t;
    for (int i = 0; i < t; i++) {
        int before, after;
        std::cin >> before >> after;
        queueController(before, after);
    }
    return 0;
}


void queueController(int before, const int& after) {
    // 초기화
    while (!q.empty()) q.pop();
    memset(visited, false, sizeof(visited));
    memset(parent, -1, sizeof(parent));
    memset(cmd, '\0', sizeof(cmd));

    // 결과 선언
    std::string result;

    // 최초 push
    q.push(before);
    visited[before] = true;
    parent[before] = -1;
    cmd[before] = '#';

    while (!q.empty()) {
        int current = q.front(); q.pop();
        if (current == after) {
            int index = current;
            while (parent[index] != -1) {
                result.push_back(cmd[index]);
                index = parent[index];
            }
            std::reverse(result.begin(), result.end());
            std::cout << result << std::endl;
            break;
        }
        rotationL(current);
        rotationR(current);
        mutlipleDouble(current);
        decreaseOne(current);
    }
}

void rotationR(const int &current) {
    int digits = 1000;
    int value = current / 10 + (current % 10) * digits;
    if (!visited[value]) {
        q.push(value);
        parent[value] = current;
        visited[value] = true;
        cmd[value] = 'R';
    }
}

void rotationL(const int &current) {
    int digits = 1000;
    int value = current / digits + (current % digits) * 10;
    if (!visited[value]) {
        q.push(value);
        parent[value] = current;
        visited[value] = true;
        cmd[value] = 'L';
    }
}

void mutlipleDouble(const int &current) {
    int value = (current * 2) % 10000;
    if (!visited[value]) {
        q.push(value);
        parent[value] = current;
        visited[value] = true;
        cmd[value] = 'D';
    }
}

void decreaseOne(const int &current) {
    int value = current - 1;
    if (value < 0) {
        value = 9999;
    }
    if (!visited[value]) {
        q.push(value);
        parent[value] = current;
        visited[value] = true;
        cmd[value] = 'S';
    }
}