BOJ 13913: 숨바꼭질 4

✔ 문제 링크

---

BOJ 13913: 숨바꼭질 4

---

✔ 문제해결전략

• 그래프 탐색
• 1차원에서의 BFS(Breadth First Search)

---

✔ 해결과정

• BOJ 1697: 숨바꼭질에서 이동경로가 추가되었다.
• BFS 하면서 각 점이 어느 점에서 -1, +1, *2 되어 탐색 대상이 되었는지를 before에 저장하고 동생 위치에서 이를 역추적하여 route에 탐색해온 경로를 담은 다음에 이를 뒤집으면 이동경로가 나온다.

---

✔ 정답 Code

#include <bits/stdc++.h>
using namespace std;

int dist[100002];
int before[100002];

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n, k;
    queue < int > q;
    cin >> n >> k;

    fill(dist, dist + 100001, -1);
    fill(before, before + 100001, -1); // new
    dist[n] = 0;
    q.push(n);
    while (!q.empty()) {
        int cur = q.front();
        q.pop();

        for (int new_: {
                cur - 1,
                cur + 1,
                2 * cur
            }) {
            if (new_ < 0 || new_ > 100000) continue;
            if (dist[new_] != -1) continue;
            dist[new_] = dist[cur] + 1;
            q.push(new_);
            before[new_] = cur; // new
        }
    }

    vector < int > route;
    int now = k;
    while (now != n) {
        route.push_back(now);
        now = before[now];
    }
    route.push_back(now); // push back n
    reverse(route.begin(), route.end());
    cout << dist[k] << '\n';

    for (int i: route) cout << i << " ";

}

---

✔ Comment

더 좋은 방법이 있을까 해서 검색해 봤는데 다들 비슷하게 푼 거 같다.