[백준 13549번] 숨바꼭질 3 (C++)

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

13549번: 숨바꼭질 3

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int N, K;
vector<int> dist(100001, MAX);

void Dijkstra()
{
    queue<int>q;
    q.push(N);
    dist[N] = 0;
    while(!q.empty())
    {
        int cur = q.front();
        q.pop();
        
        if(cur == K) return;

        if(cur - 1 >=0 && dist[cur-1] > dist[cur] + 1) //뒤로 걷기, 1초 이동
        {
            dist[cur-1] = dist[cur] + 1;
            q.push(cur-1);
        }

        if(cur + 1 <=100001 && dist[cur+1] > dist[cur] + 1) //앞으로 걷기, 1초 이동
        {
            dist[cur+1] = dist[cur] + 1;
            q.push(cur+1);
        }

        if(cur*2 <100001 && dist[cur*2] > dist[cur]) //순간이동, 0초 이동
        {
            dist[cur*2] = dist[cur];
            q.push(cur*2);
        }

    }
}

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);

    cin >> N >> K; 
    Dijkstra();
    cout << dist[K];
    
    return 0;
}

처음에 우선순위 큐로 풀었다가 다익스트라가 더 깔끔해보여서 다익스트라로 한번 더 제출했다.

걷는 방향은 앞으로 걷기, 뒤로 걷기, 순간이동 이렇게 총 3가지이다.

각각의 경우에 대해서 비용을 갱신해주고, 목표 위치에 도달했을 때 종료하고 현재 위치의 비용을 출력해준다.