[백준 13549 - C++] 숨바꼭질 3 : 다익스트라(Dijkstra)

www.acmicpc.net/problem/13549

13549번: 숨바꼭질 3

문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 0초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

 

입력

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

 

출력

수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

 

예제 입력 1 

5 17

예제 출력 1 

2

 

풀이

수빈이가 x-1,  x+1로 움직이는 데에는 1초가, x*2로 움직이는 데에는 0초가 걸린다.

다익스트라 알고리즘을 사용하여 이동시간이 최소가 되는 경우를 찾아야하는 문제이다.

3가지의 이동방식에 따라 이동하며 범위를 벗어나진 않는 지 확인하고 cost를 저장하면 된다. 이미 cost가 저장되어 있더라도 만약 새로 구한 경로의 cost보다 크다면 그것을 새로 구한 경로의 cost로 갱신해주며 진행하면된다.

실행이 끝나고 cost[k]에 저장된 값이 동생을 찾는데에 걸리는 가장 빠른 시간이다.

 

#include <iostream>
#include <cstdio>
#include <queue>
#include <vector>

using namespace std;

int cost[100001];
int X[2] = {-1, 1};

priority_queue<pair<int, int>> pq; //비용, 위치

int main(void){
    int n, k;
    int here, h_time;
    int there, t_time;
    
    scanf("%d %d", &n, &k);
    
    for(int i=0; i<100001; i++){
        cost[i] = -1;
    }
    pq.push(make_pair(0, n));
    cost[n] = 0;
    
    while(!pq.empty()){
        h_time = -pq.top().first;
        here = pq.top().second;
        pq.pop();
        
        if(h_time > cost[here])
            continue;
        for(int i=0; i<3; i++){
            if( i== 2){
                there = 2*here;
                t_time = h_time;
            }
            else{
                there = here+ X[i];
                t_time = h_time+1;
            }
            if(there < 0 || there > 100000)
                continue;
            
            if(cost[there] == -1){
                cost[there] = t_time;
                pq.push(make_pair(-t_time, there));
            }
            else if(cost[there] > t_time){
                cost[there] = t_time;
                pq.push(make_pair(-t_time, there));
            }
        }
    }
    printf("%d\n", cost[k]);
}