[백준 13913번] 숨바꼭질4

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

13913번: 숨바꼭질 4

<문제 풀이> BFS

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

1697번: 숨바꼭질

숨바꼭질 문제에서 경로가 추가된 문제입니다.

parents 배열을 만들고 방문 체크를 하면서 cur -1, cur +1, 2 * cur의 부모를 cur로 만들고

cur == k가 되는 순간에 cur의 부모를 계속 따라가면서 배열에 저장하고 역순으로 출력하면 됩니다.

 

<C++ 소스 코드>

#include <iostream>
#include <string>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <utility>
#include <climits>
using namespace std;
 
int n, k; 
int visited[100001];
int dist[100001];
int parents[100001];
vector<int> res;
int bfs() {
    queue<int> Q;
    Q.push(n);
    visited[n] = true;
    dist[n] = 0;
    parents[n] = n;
    while (!Q.empty()) {
        int cur = Q.front(); Q.pop();
        if (cur == k) {
            int s = cur;
            while (parents[s] != s) {
                res.push_back(s);
                s = parents[s];
            }
            res.push_back(s);
            return dist[cur];
        }
        if (2 * cur <= 100000 && !visited[2 * cur]) {
            Q.push(2 * cur);
            visited[2 * cur] = true;
            dist[2 * cur] = dist[cur] + 1;
            parents[2 * cur] = cur;
        }
        if (cur - 1 >= 0 && !visited[cur - 1]) {
            Q.push(cur - 1);
            visited[cur - 1] = true;
            dist[cur - 1] = dist[cur] + 1;
            parents[cur - 1] = cur;
        }
        if (cur + 1 <= 100000 && !visited[cur + 1]) {
            Q.push(cur + 1);
            visited[cur + 1] = true;
            dist[cur + 1] = dist[cur] + 1;
            parents[cur + 1] = cur;
        } 
    }
}
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    cin >> n >> k;
 
    cout << bfs() <<'\n';
    int len = res.size();
    for (int i = len - 1; i >= 0; i--) {
        cout << res[i] << " ";
    }
    return 0;
}