[백준] 13549번: 숨바꼭질

Solved.ac 골드5
https://www.acmicpc.net/problem/13549

설명

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다.
만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다.
순간이동을 하는 경우에는 0초 후에 2*X의 위치로 이동하게 된다.
수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

입력

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

출력

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

해결 Tip

알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색
• 데이크스트라
• 0-1 너비 우선 탐색

-방문한 위치와 방문할 때까지 걸린 시간을 함께 저장하고, 데이터의 순서가 시간이 적은 순으로 나열되는 자료구조를 사용한다.

• 한번 방문한 위치는 다시 방문하지 않도록 한다.

코드

#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;

int N, K;
bool check[100001];

int solve() {
    deque<pair<int,int>> pq;
    pq.push_front({0, N});

    int next_loc;
    while (!pq.empty()) {
        int now_loc = pq.front().second;
        int now_time = pq.front().first;
        pq.pop_front();

        if (check[now_loc]) continue;
        check[now_loc] = true;
        if (now_loc == K) return now_time;

        next_loc = 2 * now_loc;
        if (next_loc <= 100000 && !check[next_loc])
            pq.push_front({now_time, next_loc});
        
        next_loc = now_loc + 1;
        if (next_loc <= 100000 && !check[next_loc])
            pq.push_back({now_time+1, next_loc});
        
        next_loc = now_loc - 1;
        if (next_loc >= 0 && !check[next_loc])
            pq.push_back({now_time+1, next_loc});
    }
    return 0;
}

int main() {
    fastio;
    cin >> N >> K;
    cout << solve();
    return 0;
}