[백준][13913번] 숨바꼭질 4[cpp, c++]

백준 13913 숨바꼭질4

• https://skd03052.tistory.com/150 의 응용문제이다.
• bfs와 역추적이 필요하다.
• https://www.acmicpc.net/problem/13913

13913번: 숨바꼭질 4

• 풀이방법
  1) 부모 배열을 생성한 뒤, 큐에 넣은 값의 부모를 기록한다.
  2) ex) x-1의 부모는 x와 같이 배열에 넣으면 된다.

#include<iostream>
#include<queue>
#include<vector>
using namespace std;
queue<pair <int, int>> q;
bool check[1000001];
int parent[1000001];
int N, K;
int ans;
vector<int> v;
vector<int> path;
void bfs() {

    while (!q.empty()) {
        int x = q.front().first;
        int time = q.front().second;
        check[x] = true;
        q.pop();
        if (x == K) { // parent를 통해 역추적
            int idx = x;
            while (idx != N) {
                path.push_back(idx);
                idx = parent[idx];
            }
            cout << time << "\n";
            break;
        }
        // -1 
        if (x-1 >= 0 && x-1 <= 200000 && check[x-1] == false) {
            q.push(make_pair(x-1, time + 1));
            check[x-1] = true;
            parent[x-1] = x;
        }
        // +1 

        if (x+1 >= 0 && x+1 <= 200000 && check[x+1] == false) {
            q.push(make_pair(x+1, time + 1));;
            check[x+1] = true;
            parent[x+1] = x;
        }
        //순간이동

        if (x*2 >= 0 && x * 2 <= 200000 && check[x * 2] == false) {
            q.push(make_pair(x * 2, time + 1));
            check[x * 2] = true;
            parent[x * 2] = x;
        }
    }
}




int main(void) {
    cin >> N >> K;
    q.push(make_pair(N, 0));
    bfs();
    cout << N<< ' ';
    for (int i = path.size() - 1; i >= 0; i--)
        cout << path[i] << ' ';

    return 0;
}