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

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

 

bfs로 풀면 되는데, 어디서 왔는지를 저장하는 parent배열을 만들어서 경로를 추적했다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <list>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <limits.h>

using namespace std;
using int64 = long long;

vector<int> parent;
vector<bool> found;

bool CanGo(int pos) {
    if (pos < 0 || pos>100000) return false;
    if (found[pos]) return false;
    return true;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    found = vector<bool>(100001, false);
    parent = vector<int>(100001);
    for (int i = 0; i <= 100000; i++) {
        parent[i] = i;
    }

    int n, k;
    cin >> n >> k;
    queue<pair<int, int>> q;
    q.push({ n,0 });
    int ans = 0;
    while (!q.empty()) {
        auto curr = q.front();
        q.pop();
        if (curr.first == k) {
            ans = curr.second;
            break;
        }
        if (CanGo(curr.first - 1)) {
            q.push({ curr.first - 1,curr.second + 1 });
            found[curr.first - 1] = true;
            parent[curr.first - 1] = curr.first;
        }
        if (CanGo(curr.first + 1)) {
            q.push({ curr.first + 1,curr.second + 1 });
            found[curr.first + 1] = true;
            parent[curr.first + 1] = curr.first;
        }
        if (CanGo(curr.first * 2)) {
            q.push({ curr.first * 2,curr.second + 1 });
            found[curr.first * 2] = true;
            parent[curr.first * 2] = curr.first;
        }
    }
    vector<int> ansVec;

    while (true) {
        ansVec.push_back(k);
        if (k == n) break;
        k = parent[k];
    }

    reverse(ansVec.begin(), ansVec.end());
    cout << ans << "\n";
    for (auto a : ansVec) {
        cout << a << " ";
    }
}