BOJ 9019: DSLR 작성일 2020-03-07 https://www.acmicpc.net/problem/9019 3월동안 210문제 풀기 (14/210) 무난한 BFS, 풀고 직접 돌려보니 숫자를 기가막히게 찾아감 2를 220으로 만들려면 2->4->8->16->6001->2002->22->220 아주 재미났음 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657#include <bits/stdc++.h> using namespace std; struct Node { int v, par; char cmd; }; string bfs(int s, int e) { vector<Node> qq(20000); int rp = 0, wp = 0; vector<int> visit(10000); auto push = [&](Node n) { qq[wp++] = n; }; auto pop = [&]() { return qq[rp++]; }; push({s, -1, 0}); while(rp != wp) { Node cur = pop(); int v = cur.v; if(v == e) { push(cur); break; } int db = v * 2 % 10000; if(!visit[db]) push({db, rp-1, 'D'}), visit[db] = 1; int dec = (10000+v-1)% 10000; if(!visit[dec]) push({dec, rp-1, 'S'}), visit[dec] = 1; int ls = v*10%10000 + v*10/10000; if(!visit[ls]) push({ls, rp-1, 'L'}), visit[ls] = 1; int rs = v/10 + (v%10)*1000; if(!visit[rs]) push({rs, rp-1, 'R'}), visit[rs] = 1; } Node& cur = qq[wp-1]; string ans; while(cur.v != s) { ans += cur.cmd; cur = qq[cur.par]; } reverse(ans.begin(), ans.end()); return ans; } int main() { ios::sync_with_stdio(false); int TC, a, b; cin >> TC; while(TC--) { cin >> a >> b; cout << bfs(a,b) << '\n'; } }