[BOJ] 13549번 - 숨바꼭질 3

백준 13549번 - 숨바꼭질 3

시간제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	512 MB	19622	5890	3680	26.760%

문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 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

출처

www.acmicpc.net/problem/13549

13549번: 숨바꼭질 3

알고리즘 분류

• 그래프 이론
• 자료 구조
• 그래프 탐색
• 너비 우선 탐색
• 다익스트라
• 0-1 너비 우선 탐색

접근 방법

현재 수빈이가 위치한 곳을 X라고 가정해보자.

먼저 수빈이가 현재 위치 X까지 올 때까지 걸린 시간과 동일한 시간이 걸리는 좌표는 X, 2X, 4X, 8X, ...

( until kX <= 100,000 , k는 상수)가 될 것이다.

그러면 ( X ~ 2X 사이의 있는 좌표로 가기 위한 최소 시간 ), ( 2X ~ 4X 사이의 있는 좌표로 가기 위한 최소 시간 ), ... 은 어떻게 구할 것인가?

 

특정 위치 K부터 시작하여 K+1, K-1, 2*K를 그래프의 정점으로 보고 해당 위치로 가기 위한 추가 시간을 간선으로 본다면 위 문제는 수빈이가 출발한 위치 N 으로 부터 특정 위치 K까지의 최단 경로가 된다. 

따라서, 그래프의 특정 정점에서 ~ 도착 위치까지의 최단 경로를 구하는 탐색 알고리즘을 쓰면 되겠다. 

필자는 다익스트라 알고리즘을 활용하여 구현하였다. 

다익스트라 알고리즘을  Priority Queue를 이용하면, O(|E|log|V|)으로 해결 할 수 있는데 필자가 아래에 구현한 코드에서 탐색 횟수는 최대 (2-1) + (4-2) + (8-4) + (16 - 8) + .... + (65536 - 32768) = ${2^{16} - 1}$ 번을 넘지않는다( X가 1일 때가 최악의 경우 ). 즉 다익스트라 알고리즘으로 충분히 풀 수 있다. 

 

로직은 다음과 같다.

먼저 { 현재 위치까지 오는데 걸린 시간, 현재 위치 } 쌍을 우선순위 큐에 넣어준다. 

만약, 현재 위치까지 오는데 걸린 시간이 이전에 구했던 최소 시간보다 더 작다면 이 경로로 탐색을 진행하는 것이 의미가 없으므로 탐색을 중단한다. 해당 작업을 반복한다면 수빈이가 출발한 위치(N)부터 특정 지점(K)까지의 최단경로를 알 수 있게 된다.

 

소스 코드

#include <bits/stdc++.h>
using namespace std;
int N, K;
int main(void){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    cin >> N >> K ;

    int dist[200001];
    for(auto& it : dist) it = 1e9;

    dist[N] = 0;

    // { 현재 위치 까지 오는데 걸린 시간, 현재 위치 }
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> PQ;
    PQ.push({0, N});

    while(!PQ.empty()){
        auto top = PQ.top(); PQ.pop();
        int cost = top.first, pos = top.second;

        if( cost > dist[pos] ) continue;

        int nPos = pos + 1;
        if( 0 <= nPos && nPos <= 200000 && dist[nPos] > dist[pos] + 1 ){
            dist[nPos] = dist[pos] + 1;
            PQ.push({cost+1, nPos});
        }
        nPos = pos - 1;
        if( 0 <= nPos && nPos <= 200000 && dist[nPos] > dist[pos] + 1 ){
            dist[nPos] = dist[pos] + 1;
            PQ.push({cost+1, nPos});
        }
        nPos = pos * 2;
        if( 0 <= nPos && nPos <= 200000 && dist[nPos] > dist[pos]  ){
            dist[nPos] = dist[pos] ;
            PQ.push({cost, nPos});
        }
    }
    cout << dist[K] ;
    return 0;
}