(매일 BOJ) C++ 13913번 숨바꼭질 4

이번 문제는 13913번 숨바꼭질 4이다

문제 요약

N에서 K로 이동할 때 가능한 연산은 x-1, x+1, x*2.
모든 연산 비용이 1이므로 가중치가 없는 그래프의 최단거리 문제이고, 정석은 BFS이다

 

접근법

• BFS(너비 우선 탐색): 시작점 N에서 한 단계씩 확장하면, 처음 K를 만나는 순간의 깊이가 곧 최단 시간
• 방문 체크: 큐에 삽입(push)할 때 visited[next]=true로 표시해 중복 탐색 방지
• 부모 추적(parent 배열): parent[next] = x로 “어디서 왔는지” 기록해 두고, K를 찾으면 parent를 거슬러 올라가 경로를 복원
• 경로 정방향으로 출력: 역추적은 K → … → N이므로 reverse로 뒤집어 N → … → K로 출력

작성코드

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

int N,K;

pair<int,vector<int>> BFS ();

int main (void){
    cin >> N >> K;

    auto [a,b] = BFS();

    cout << a << '\n';
    for(int i : b){
        cout << i << ' ';
    }
}

pair<int, vector<int>> BFS (){
    vector<bool> visited(100001,false);
    vector<int> parent(100001,-1);
    queue<pair<int, int>> q;
    q.push({N,0});
    visited[N] = true;
    parent[N] = N;
 
    while(!q.empty()){
        int x = q.front().first;
        int time = q.front().second;
        q.pop();

        if(x == K){
            vector<int> path; 
            for (int cur = K;; cur = parent[cur]){
                path.push_back(cur);
                if (cur == N) break;
            }
            reverse(path.begin(),path.end());
            return {time, path};
        }

        for(int next : {x-1,x+1,x*2}){
            if (next < 0 || next > 100000) continue;
            if (visited[next]) continue;
            visited[next] = true;
            parent[next] = x;
            q.push({next, time + 1});
        }
    }

}