발상
만들 수 있는 수는 로 제한되어 있으므로 BFS 탐색할 때 이미 방문한 수는 다시 방문할 필요가 없다. 별도의 발상이 없이도 주어진 경로를 BFS 탐색해 순차적으로 방문하고 현재 만든 수 이전에 방문한 수를 기록하는 것으로 역추적까지 무리 없이 할 수 있다.
점화식
탐색 가지수가 조금 많긴 하다. D연산을 할 때 을 만드는 경우는 과 두가지이기 때문에 이 점을 주의해야한다.와 는 각각 Left Shift 연산과 Right Shift 연산을 의미한다.
역추적
특이하게 연산마다 특정한 문자로 치환해서 출력하기를 요구한다. 이런 경우, 연산의 종류를 추가로 dp 배열에 추가해두면 코드를 명료하게 작성할 수 있다.
#include <iostream>
#include <stack>
#include <vector>
#include <queue>
using namespace std;
// c : 현재 수
// v : 현재 수를 만들기 위해 진행한 연산 횟수
// p : 현재 수의 이전 수
// rp : 현재 수를 만들기 위해 마지막으로 사용한 연산
struct node {
int c, v, p;
char rp;
};
void printpath(int c, vector<node>& dp) {
if (dp[c].p == -1) return;
printpath(dp[c].p, dp);
cout << dp[c].rp;
}
int main()
{
int tc; cin >> tc;
while (tc--) {
int n, m; cin >> n >> m; vector<node> dp(10000, { -1, -1, -1 });
queue<node> q; q.push({ n, 0, -1, 'x'});
dp[n].v = 0;
dp[n].p = -1;
dp[n].rp = 'x';
while (!q.empty()) {
auto cur = q.front(); q.pop();
vector<int> nx // 다음 수 후보 리스트
{
cur.c * 2 % 10000, // D 연산
cur.c - 1 >= 0 ? cur.c - 1 : 9999, // S 연산
cur.c / 1000 + (cur.c % 1000) * 10, // L 연산
cur.c % 10 * 1000 + (cur.c / 10) // R 연산
};
vector<char> nxc{ 'D', 'S', 'L', 'R' }; // 연산 타입 문자
int sign = 0;
for (int i = 0; i < 4; i++) {
int np = nx[i];
if (dp[np].v == -1) { // 한번도 만들어진적이 없는 수라면 갱신
dp[np].v = cur.v + 1; // 연산 횟수
dp[np].p = cur.c; // 만든 수의 이전 수(=현재 수)
dp[np].rp = nxc[i]; // 연산 타입
if (np == m) {
sign = 1;
break;
}
q.push({ np, cur.v + 1, cur.c, nxc[i] });
}
}
if (sign == 1) break;
}
printpath(m, dp);
cout << "\n";
}
return 0;
}