발상
BFS 탐색을 하며 경로에 대한 최단 거리를 기록하면 된다. 모든 이동의 거리는 1로 취급되기 때문에(횟수 1회로 이동) BFS 탐색 특성상 이미 방문한 위치를 다시 방문하는 경우 절대 최단 거리가 될 수 없다. 따라서 첫 방문에만 최단 거리와 현재 이전에 있었던 위치 2가지를 기록한다. 이후 역추적할 때 동생의 위치 에서 시작해 이전에 방문한 위치들을 거슬러 올라가며 위치를 출력한다.
점화식
역추적
출발한 에 도착할 때 까지 현재 위치 이전의 위치를 거슬러가며 위치를 출력한다.
코드
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
// c : 현재 위치
// v : 이동 횟수
// p : 이전 위치
struct node {
int c, v, p;
};
void printpath(int c, vector<node>& dp) {
if (dp[c].p == -1) {
cout << c << " ";
return;
}
printpath(dp[c].p, dp);
cout << c << " ";
}
int main() {
int n, k; cin >> n >> k; vector<node> dp((int)(1e5 + 1), node { -1, (int)21e8, -1 });
if (n == k) cout << 0 << "\n";
dp[n] = { n, 0, -1 };
queue<node> q; q.push({ n, 0, -1 });
while (!q.empty()) {
auto cur = q.front(); q.pop();
if (cur.c + 1 <= 1e5 && dp[cur.c + 1].v > cur.v + 1) {
dp[cur.c + 1].v = cur.v + 1;
dp[cur.c + 1].p = cur.c;
if (cur.c + 1 == k) {
cout << cur.v + 1;
break;
}
q.push({ cur.c + 1, cur.v + 1, cur.c });
}
if (cur.c - 1 >= 0 && dp[cur.c - 1].v > cur.v + 1) {
dp[cur.c - 1].v = cur.v + 1;
dp[cur.c - 1].p = cur.c;
if (cur.c - 1 == k) {
cout << cur.v + 1;
break;
}
q.push({ cur.c - 1, cur.v + 1, cur.c });
}
if (cur.c * 2 <= 1e5 && dp[cur.c * 2].v > cur.v + 1) {
dp[cur.c * 2].v = cur.v + 1;
dp[cur.c * 2].p = cur.c;
if (cur.c * 2 == k) {
cout << cur.v + 1;
break;
}
q.push({ cur.c * 2, cur.v + 1, cur.c });
}
}
cout << "\n";
printpath(k, dp);
return 0;
}