백준 9019 - DSLR(C++)

문제

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

9019번: DSLR

 

풀이

처음 생각한 방식은

#include <iostream>
#include <queue>

using namespace std;
int a, b;

void bfs() {
    queue<pair<int, string>> q;
    q.push({a, ""});

    while (!q.empty()) {
        int tmp;
        int x = q.front().first;
        string op = q.front().second;
        q.pop();

        if (x == b) {
            cout << op << '\n';
            return;
        }

        tmp = (2 * x) % 10000; // D
        q.push({tmp, op + "D"});

        tmp = x - 1; // S
        if (tmp == -1) tmp = 9999;
        q.push({tmp, op + "S"});

        tmp = (x % 1000) * 10 + x / 1000; // L
        q.push({tmp, op + "L"});

        tmp = (x % 10) * 1000 + x / 10; // R
        q.push({tmp, op + "R"});

    }
}

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a >> b;
        bfs();
    }
}

각 연산 결과마다 DSLR 연산해 주면 되겠다고 생각했고,

방문체크 없이 연산한 모든 숫자를 큐에 넣어줘도 된다고 생각했음

하지만 메모리 초과. 방문한 숫자는 표시해줘야 함

 

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

while (!q.empty()) {
    int tmp;
    int x = q.front().first;
    string op = q.front().second;
    q.pop();

    if (x == b) {
        cout << op << '\n';
        return;
    }
}

이렇게 큐에 숫자랑 연산 내역을 같이 저장하는 것을 생각을 못해서 헤맸다..

이것만 생각해낼 수 있었으면 은근히 쉽게 풀 수 있었을 듯 ㅜㅜ

 

코드

#include <iostream>
#include <queue>

using namespace std;
int a, b;
bool visited[10000];

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

    while (!q.empty()) {
        int tmp;
        int x = q.front().first;
        string op = q.front().second;
        q.pop();

        if (x == b) {
            cout << op << '\n';
            return;
        }

        tmp = (2 * x) % 10000;
        if(!visited[tmp]) {
            visited[tmp]= true;
            q.push({tmp, op + "D"});
        }

        tmp = x - 1;
        if (tmp == -1) tmp = 9999;
        if(!visited[tmp]) {
            visited[tmp]= true;
            q.push({tmp, op + "S"});
        }

        tmp = (x % 1000) * 10 + x / 1000;
        if(!visited[tmp]) {
            visited[tmp]= true;
            q.push({tmp, op + "L"});
        }

        tmp = (x % 10) * 1000 + x / 10;
        if(!visited[tmp]) {
            visited[tmp]= true;
            q.push({tmp, op + "R"});
        }

    }
}

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a >> b;
        bfs();
        fill_n(visited,10000,false);
    }
}