[백준] 9019번 : DSLR

문제

 

---

풀이

 

문제 자체는 그냥 간단한 BFS였는데 그 과정이 너무 더럽다고 해야하나 짜증나게 한다고 해야하나 암튼 그랬다.

D, S까지는 그렇다고 치고 L, R을 구현하는게 문제인데, 제일 먼저 생각난건 string이라 그걸로 했더니 tle가 났다.

그러다가 잘 생각해보니 이거 그냥 수학으로 되는 연산이었다...이것만 빨리 알아챘어도..

---

소스코드

 

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <utility>

using namespace std;

string bfs(int source, int target) {
    vector<bool> visited;
    visited.assign(10000, false);
    queue<pair<int, string>> q;

    visited[source] = true;
    q.push(make_pair(source, ""));
    while (!q.empty()) { //벡터로 처리하려고 했는데 벡터 하나 썼다고 TLE 발생
        int cur = q.front().first;
        string str = q.front().second;
        q.pop();

        if (cur == target) //target 찾음
            return str;
        int next_num;

        next_num = (2 * cur) % 10000; //D
        if (!visited[next_num]) {
            visited[next_num] = true;
            q.push(make_pair(next_num, str + "D"));
        }

        next_num = (cur - 1 < 0) ? 9999 : cur - 1; //S
        if (!visited[next_num]) {
            visited[next_num] = true;
            q.push(make_pair(next_num, str + "S"));
        }

        next_num = ((cur % 1000) * 10) + (cur / 1000); //L
        if (!visited[next_num]) {
            visited[next_num] = true;
            q.push(make_pair(next_num, str + "L"));
        }

        next_num = ((cur % 10) * 1000) + (cur / 10); //R
        if (!visited[next_num]) {
            visited[next_num] = true;
            q.push(make_pair(next_num, str + "R"));
        }
    }
    return "";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int T, A, B;

    cin >> T;
    for (int i = 0; i < T; i++) {
        cin >> A >> B;
        cout << bfs(A, B) << '\n';
    }
}

전체 소스코드다. next_num을 저런식으로 하고 싶지 않아서

모든 next_num들을 벡터에 넣고 for문을 돌며 하려 했는데 TLE를 뱉어냈다. 세상에 마상에...

문제가 좀 지저분할 뿐이지 어려운 구석은 없어서 설명은 굳이 하지 않겠다.