[BOJ] 9019. DSLR

* 경로를 남기고, 역추적한다. 

* visited[i] = j 는 i가 되기 전의 숫자가 j임을 표시한다. 

op[i] = i가 되기 위한 연산을 저장한다.

* a = 시작점 일 때, visited[a] = -2로 저장한다. (이 표식을 발견하면 역추적을 중지한다.)

* a가 b가 되었을 때, 역추적을 하면서 벡터에 사용한 연산들을 저장한다. 

* a가 b가 아니라면, D ,S, L, R 연산을 진행하면서 만들어진 숫자들을 모두 큐에 넣는다. 

중복 탐색을 방지하기 위해 이미 한 번 생성된 숫자는 더 이상 탐색하지 안흔ㄴ다. 

* 이 문제는 L, R 연산을 효율적으로 작성하는 게 중요하다. 

deque, string 등은 시간이 초과된다. 

L : d2 d3 d4 d1 이므로 가장 마지막 숫자를 추출한다. (n = num / 1000)

나머지 d2, d3, d4 를 구한 후에 (tmp = num % 1000) 자리수를 늘려준다. (*10) 

두 수를 더한다. 

n + tmp

int n = next / 1000; int tmp = (next % 1000) * 10; next = tmp + n;

 

R : d4 d1 d2 d3 이므로 가장 마지막 숫자를 가져온다. (n = num % 10)

나머지 d1,d2,d3을 구한 후에 n * 1000  + d1,d2,d3를 한다. 

int n = next % 10; int tmp = next / 10; next = 1000 * n + tmp;

 

 

#include <iostream> #include <vector> #include <queue> #include <deque> #include <algorithm> #define MAXX 9999 #define MINN 0 using namespace std; //BOJ https://www.acmicpc.net/problem/9019 int visited[MAXX + 1]; char op[MAXX + 1]; void bfs(int start, int dest) { queue<int> q; q.push(start); visited[start] = -2; //경로의 시작 => 이전 경로 while (!q.empty()) { int now = q.front(); q.pop(); if (now == dest) { //경로 역추적 vector<char> res; int pos = now; while (1) { res.push_back(op[pos]); pos = visited[pos]; if (visited[pos] == -2) break; } for (int i = res.size() - 1; i >= 0; i--) { cout << res[i]; } cout << '\n'; return; } // cout << now << '\n'; for (int i = 0; i < 4; i++) { int next = now; if (i == 0) { //D next *= 2; if (next > MAXX) { next %= 10000; } if (visited[next] != -1 || visited[next] == -2) continue; visited[next] = now; op[next] = 'D'; q.push(next); } else if (i == 1) { next -= 1; if (next < MINN) { next = MAXX; } if (visited[next] != -1 || visited[next] == -2) continue; visited[next] = now; op[next] = 'S'; q.push(next); } else if (i == 2) { //l int n = next / 1000; int tmp = (next % 1000) * 10; next = tmp + n; if (visited[next] != -1 || visited[next] == -2) continue; visited[next] = now; op[next] = 'L'; q.push(next); } else if (i == 3) { int n = next % 10; int tmp = next / 10; next = 1000 * n + tmp; if (visited[next] != -1 || visited[next] == -2) continue; visited[next] = now; op[next] = 'R'; q.push(next); } } } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); int t; cin >> t; while (t--) { int a, b; cin >> a >> b; //a-> b로 만들기 for (int i = 0; i < MAXX + 1; i++) { visited[i] = -1; } bfs(a, b); } return 0; }