(c++) 13549번: 숨바꼭질3 다익스트라 코드

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

13549번: 숨바꼭질 3

 

 

---

 

 

13549번: 숨바꼭질3

 

BFS를 이용하여 풀 수도 있고, 다익스트라로 풀 수 있는 문제이다.

 

아래 코드는 다익스트라로 푼 것이다.

 

기존의 다익스트라 코드에서 

 

앞 뒤로 한 칸 이동과 두 배로 이동하는 것을 각각 구현하여 코드 가독성을 높여보았다.

 

 

문제를 보면 숫자 한 칸 간격으로 무향 간선으로 이어져 있고, 각 숫자의 두 배의 숫자에 유향 간선이 있다.

 

4 →2 처럼 반대로 가는 경우는 없다.

 

간선으로 봤을 때

 

 

위 그림과 같은 상태로 쭉 이어진다고 생각하면 다익스트라로 충분히 해결할 수 있다.

 

따로 vector<pair<int, int> > graph[100001];

 

같이 간선 정보를 넣을 필요없이

 

다익스트라 알고리즘 안에 정보를 넣는다면 더욱 간편하게 코드를 짤 수 있다.

 

N이 K보다 큰 경우가 있을 수 있어서 조건문으로 앞에서 바로 처리할 수 있게 했다.

(테스트 시간에는 영향이 없는 듯 하다.

 

#include <bits/stdc++.h>
#define INF 100010

using namespace std;

int N, K;

vector<int> dist(100001, INF);

void dijkstra(int start) {
    dist[start] = 0;
    priority_queue<pair<int, int> > pq;
    pq.push({0, start});
    while(!pq.empty()) {
        int cost = -pq.top().first;
        int here = pq.top().second;
        pq.pop();
        if(dist[here] < cost) continue;
        if (here + 1 <= 100000) {
            if (cost + 1 < dist[here + 1]) {
                dist[here + 1] = cost + 1;
                pq.push({-(cost+1), (here + 1)});   
            }
        }
        if (here - 1 >= 0) {
            if (cost + 1 < dist[here - 1]) {
                dist[here - 1] = cost + 1;
                pq.push({-(cost+1), (here - 1)});
            }
        }
        if (here * 2 <= 100000) {
            if (cost < dist[here * 2]) {
                dist[here * 2] = cost;
                pq.push({-cost, (here * 2)});
            }
        }
    }
}
int main(void) {
    cin >> N >> K;
    if (N >= K) {
        cout << N - K;
        return 0;
    } else {
        dijkstra(N);
        cout << dist[K];
        return 0;
    }
}