[백준 9019] DSLR

A. 접근법

기본적인 BFS로 문제를 해결하였습니다.

하지만 처음에 문제를 풀었을 때 TLE를 받았습니다. 처음 문제를 풀 때 명령어를 int형 vector로 문제를 풀어 답을 출력할 때 해당 vector를 O(N)으로 탐색하며 출력을 한 것이 시간초과의 원인이었던 것 같습니다.

BFS 탐색이 단위가 되는 node내에 진행된 명령어를 string으로 저장하고 있고 목적지에 도달하면 구한 s를 출력해줌으로써 불필요한 탐색시간을 지우니 통과를 했습니다.

B. 구현

struct node {
int x;
string s;
node(int a, string ts) {
this->x = a;
this->s.clear();
string cp(ts);
this->s = cp;
}
};

BFS 탐색이 단위가 되는 node는 정수 x와 x를 얻기 위해 진행된 명령어 s로 구성되어 있습니다.

int dslr(int n, int d)

숫자 n에 대해서 d(=0[D],1[S],2[L],3[R])에 대한 명령어 수행결과를 반환하는 함수입니다.
문제 지문에 충실하게 해당 함수를 구현하였습니다.

C. 코드

#include<iostream>
#include<vector>
#include<cstring>
#include<queue>

using namespace std;

int T, A, B;
bool visit[10000];
struct node {
    int x;
    string s;
    node(int a, string ts) {
        this->x = a;
        this->s.clear();
        string cp(ts);
        this->s = cp;
    }
};
queue<node> q;
int dslr(int n, int d) {
   if(d == 0) {
        if(2*n > 9999)
            return (2*n)%10000;
        else
            return 2*n;
    }
    else if(d == 1) {
        if(n == 0)
            return 9999;
        else
            return n-1;

    }
    else if(d == 2) {
        int d1 = n/1000;
        n %= 1000;
        int d2 = n/100;
        n %= 100;
        int d3 = n/10;
        n %= 10;
        int d4 = n/1;

        return d2 * 1000 + d3 * 100 + d4 * 10 + d1;
    }
    else if(d == 3) {

        int d1 = n/1000;
        n %= 1000;
        int d2 = n/100;
        n %= 100;
        int d3 = n/10;
        n %= 10;
        int d4 = n/1;

        return d4 * 1000 + d1 * 100 + d2 * 10 + d3;
    }
    else {return -1;}
}
string bfs() {
    while(!q.empty()) {
        int x = q.front().x;
        string ret = q.front().s;

        q.pop();

        if(x == B)
            return ret;

        for(int i = 0; i < 4; i++) {
            int num = dslr(x, i);
            if(num >= 0 && num < 10000 && !visit[num]) {
                string temp(ret);
                visit[num] = true;
                if(i == 0)
                    temp += 'D';
                else if(i == 1)
                    temp += 'S';
                else if(i == 2)
                    temp += 'L';
                else if(i == 3)
                    temp += 'R';
                else {}
                q.push(node(num, temp));
            }
        }
    }
}
int main() {

    scanf("%d", &T);
    for(int tc = 0; tc < T; tc ++) {

        scanf("%d %d", &A, &B);
        memset(visit, 0, sizeof(bool)*10000);

        visit[A] = true;
        while(!q.empty())
            q.pop();
        string tmp = "";
        q.push(node(A, tmp));
        cout << bfs() << endl;
        
    }
    return 0;
}

D. 결과