13913번: 숨바꼭질 4

[stopmin]

문제

• 문제 링크: https://www.acmicpc.net/problem/13913

문제 풀이

해당 문제는 사실 저번에 조건이 있는 숨바꼭질 문제를 풀었었습니다! (아마도 흔한 유형인듯..!)
기존 BFS랑 유사하게 풀이가 되지만, 다른 점은 경로를 기억해야한다는 점입니다. 추가적으로 parent라는 array를 추가해주었고, 이전의 위치를 해당 array에 저장해줍니다.

이 풀이가 가능한 결정적인 그래프 적인 특징은, BFS는 방문 순서가 빠르면 그 곳에 이르기까지 최단 경로로 도착한것이 자명합니다. 따라서 도착한 기록이 없다(-1)이면 반드시 해당 경로가 최단 경로(시간)이니 parent로 두어도 무방합니다. 해당 특징이 있기에 해당 풀이에 당위성이 생기는 듯 합니다.

가장 중요한점은!!

BFS는 방문 순서가 빠르면 그 경로가 최단 경로임을 보장함.

라는 점... 이것만 알면 쉽게 풀리는 문제였습니다.

최종 코드

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

int n, k;
int arr[200001]; // 시간
int parent[200001]; // 경로

void bfs(int start) {
    queue<int> q;
    q.push(start);
    arr[start] = 0;
    parent[start] = -1;

    while (!q.empty()) {
        int curr = q.front();
        q.pop();
        if (curr == k) return;
        for (int next : {curr - 1, curr + 1, curr * 2}) {
            if (next >= 0 && next <= 200000 && arr[next] == -1) {
                arr[next] = arr[curr] + 1;
                parent[next] = curr;
                q.push(next);
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> k;
    fill(arr, arr + 200001, -1);
    fill(parent, parent + 200001, -1);

    bfs(n);
    cout << arr[k] << "\n";

    vector<int> path;
    for (int i = k; i != -1; i = parent[i]) path.push_back(i);

    reverse(path.begin(), path.end());

    for (int i : path) cout << i << " ";
}