기본적인 BFS로 문제를 해결하였습니다.
하지만 처음에 문제를 풀었을 때 TLE를 받았습니다. 처음 문제를 풀 때 명령어를 int형 vector로 문제를 풀어 답을 출력할 때 해당 vector를 O(N)으로 탐색하며 출력을 한 것이 시간초과의 원인이었던 것 같습니다.
BFS 탐색이 단위가 되는 node내에 진행된 명령어를 string으로 저장하고 있고 목적지에 도달하면 구한 s를 출력해줌으로써 불필요한 탐색시간을 지우니 통과를 했습니다.
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])에 대한 명령어 수행결과를 반환하는 함수입니다.
문제 지문에 충실하게 해당 함수를 구현하였습니다.
#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;
}