숨바꼭질 3 13549

문제

접근 방법

2배로 이동하는 경우, 1을 더하는 경우, 1을 빼는 경우가 있다.
우선순위 큐를 활용하면 최소 비용인 것부터 가져올 수 있으니 최소 비용인 것에 값을 수정해나가며 답에 다가가면 된다.

코드

#include <iostream>
#include <queue>
#include <vector>
#define maxNum 100001
using namespace std;
bool isVisted[maxNum];
int dx[] = {1, -1};
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    int N, K;
    cin >> N >> K;
    pq.push({0, N});
    while (!pq.empty())
    {
        auto cur = pq.top();
        if (cur.second == K)
            break;
        pq.pop();
        int nextNum = cur.second << 1;
        if (nextNum < maxNum && !isVisted[nextNum])
        {
            isVisted[nextNum] = true;
            pq.push({cur.first, nextNum});
        }
        for (int i = 0; i < 2; ++i)
        {
            nextNum = cur.second + dx[i];
            if (nextNum >= 0 && nextNum < maxNum && !isVisted[nextNum])
            {
                isVisted[nextNum] = true;
                pq.push({cur.first + 1, nextNum});
            }
        }
    }
    cout << pq.top().first;
    return 0;
}

풀이

실수로 0 이하인 경우를 확인 안 해줘서 틀렸다.