[C++]백준 13913번 숨바꼭질 4

📌문제 링크

---

https://www.acmicpc.net/problem/13913

📌문제 설명

---

bfs탐색을 하며 경로 배열에 경로를 기록해주면 된다.

📌코드

---

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <climits>
using namespace std;

int N, K;                 // 수빈이 위치와 동생 위치
int load[100001];         // 최소 시간 저장
int previous[100001];     // 경로 추적용

void input() {
    cin >> N >> K;
}

void bfs() {
    fill(load, load + 100001, INT_MAX); // 최소 시간 초기화
    queue<int> q;

    q.push(N);          // 시작점
    load[N] = 0;        // 시작점 시간 0
    previous[N] = -1;   // 시작점의 이전 경로 없음

    while (!q.empty()) {
        int current = q.front();
        q.pop();

        if (current == K) { // 도착 시 경로와 시간 출력
            cout << load[K] << '\n';

            vector<int> path;
            for (int cur = K; cur != -1; cur = previous[cur]) {
                path.push_back(cur);
            }
            reverse(path.begin(), path.end());

            for (int p : path) {
                cout << p << " ";
            }
            cout << '\n';
            return;
        }

        // 순간이동 (×2) 처리
        if (current * 2 <= 100000 && load[current * 2] > load[current] + 1) {
            load[current * 2] = load[current] + 1;
            previous[current * 2] = current;
            q.push(current * 2);
        }

        // 걷기 (+1)
        if (current + 1 <= 100000 && load[current + 1] > load[current] + 1) {
            load[current + 1] = load[current] + 1;
            previous[current + 1] = current;
            q.push(current + 1);
        }

        // 걷기 (-1)
        if (current - 1 >= 0 && load[current - 1] > load[current] + 1) {
            load[current - 1] = load[current] + 1;
            previous[current - 1] = current;
            q.push(current - 1);
        }
    }
}

void solve() {
    input();
    bfs();
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    solve();
    return 0;
}