Baekjoon 13549번 숨바꼭질 3

문제

https://www.acmicpc.net/problem/13549

걸린 시간

-

풀이

C++

#include <bits/stdc++.h>
#define INF 1e9
#define all(c) c.begin(), c.end()
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int N, K;
    cin >> N >> K;
    vector<int> dist(200001, INF);
    priority_queue<pii> pq;
    pq.push({0, N});
    dist[N] = 0;
    while(!pq.empty()){
        int cost = -pq.top().first;
        int here = pq.top().second;
        pq.pop();
        pii adj[3] = {{here-1, 1}, {here+1, 1}, {here*2, 0}};
        for(int i = 0; i < 3; i++){
            int there = adj[i].first;
            int nextDist = cost + adj[i].second;
            if(there < 200001 && nextDist < dist[there]){
                dist[there] = nextDist;
                pq.push({-nextDist, there});
            }
        }
    }
    cout << dist[K] << "\n";
    return 0;
}

좌우로 이동하려면 1초가 걸리지만 순간이동에는 시간이 소요되지 않는다. 이는 간선의 가중치가 다른 최단 경로 찾기 문제이므로 다익스트라 알고리즘을 적용하면 해결할 수 있다.

간선의 가중치가 0과 1로 만 이루어져 있기 때문에 0-1 bfs 알고리즘을 사용해서도 풀이할 수 있다고 한다.