[골5] 13549 - 숨바꼭질 3

#include <limits.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;
using IntPair = pair<int, int>;

#define MAX 100001

bool vis[MAX];

int MinSec(int n, int k)
{
    priority_queue < IntPair, vector<IntPair>, greater<IntPair>> q;

    // 경과 시간을 기준으로 우선순위 큐 (짧을수록 우선순위 크다)
    q.push({ 0, n });
    vis[n] = true;

    while (!q.empty())
    {
        auto top = q.top(); q.pop();
        int curSec = top.first, curLoc = top.second;
        
        // 목적지 도달
        if (curLoc == k)
            return curSec;

        // 세 가지 경우의 수
        if (curLoc * 2 < MAX &&
            !vis[curLoc * 2])
        {
            q.push({ curSec, curLoc * 2 });
            vis[curLoc * 2] = true;
        }
        if (curLoc + 1 < MAX &&
            !vis[curLoc + 1])
        {
            q.push({ curSec + 1, curLoc + 1 });
            vis[curLoc + 1] = true;
        }
        if (curLoc - 1 >= 0 &&
            !vis[curLoc - 1])
        {
            q.push({ curSec + 1, curLoc - 1 });
            vis[curLoc - 1] = true;
        }
    }
}

int main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n, k; cin >> n >> k;
    cout << MinSec(n, k);
    return 0;
}