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

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는 정수이다.

 

 

 

 

출력 :

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

 

 

 

 

 

풀이)

 

#include <iostream>
#include <vector>
#include <queue>
 
#define INF 999999999
 
using namespace std;
 
int n, k;
int dist[300000];
 
// 다익스트라를 통해 최단 경로를 구한다
int dijkstra()
{
    // 우선순위 큐 사용 (가까운 순으로 정렬시킨다)
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push(make_pair(0, n));
    dist[n] = 0;
 
    int t = 0;
    while (!pq.empty())
    {
        int d = pq.top().first;
        int x = pq.top().second;
        pq.pop();
        
        // 구한 값이 이미 구한 값보다 크다면 continue
        if (dist[x] < d) continue;
 
        // 동생을 찾았다면 값을 리턴해준다.
        if (x == k) return dist[k];
 
        // 이동하는 방법은 3가지가 있으므로
        for (int j = 0; j < 3; j++)
        {
            int nx, nd;
            
            //    뒤로 걷는다
            if (j == 0)
            {
                nx = x - 1;
                nd = d + 1;
            }
            // 앞으로 걷는다
            else if (j == 1)
            {
                nx = x + 1;
                nd = d + 1;
                    
            }
            // 순간이동 한다
            else if (j == 2)
            {
                nx = x * 2;
                nd = d;
            }
 
            // 범위를 벗어났다면 continue
            if (nx < 0 || nx >= 300000) continue;
            
            // 기존 시간보다 빠르게 도착했다면 갱신해주고
            // 해당 시간과 좌표를 우선순위 큐에 넣어준다.
            if (nd < dist[nx])
            {
                dist[nx] = nd;
                pq.push(make_pair(nd, nx));
            }
        }
    }
}
 
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
 
    cin >> n >> k;
    fill(dist, dist + 300000, INF);
    
    cout << dijkstra();
 
    return 0;
}
 

---

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

13549번: 숨바꼭질 3