백준 13549 - 숨바꼭질 3

문제 설명

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

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

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

---

 

 

 

 

 

 

제한 사항

---

 

 

 

 

 

 

풀이

문제를 요약하면, N에서 K로 이동할 때, 가장 짧은 이동 시간을 구하는 것이다.

N에서 K로 이동하는 방법은 걸어가면 1초를 소비하여 ±1칸을 움직일 수 있고 0초를 소비하여 ×2칸에 도착할 수 있다.

 

DP와 BFS를 이용하면 간단하게 해결할 수 있다.

N에서 출발하여 이동할 수 있는 칸에 도착하면 해당 칸에 도착하는 최소 시간을 갱신하며 BFS를 진행한다.

만약 기록된 최소 시간보다 더 오래 걸렸다면 더 이상 분기를 진행하지 않는다.

 

주의해야 할 점은 N과 K로만 이동할 수 있는 최대 영역을 설정해서는 안된다는 점이다.

무슨 말이냐면 N이 4이고 K가 7일 때 0~7까지만 이동할 수 있는 게 아니라 8로 이동하여 한 칸 뒤로 가도 된다는 뜻이다.

따라서, 최대값인 $100,000$으로 이동 영역을 설정해 주면 된다.

---

 

 

 

 

 

전체 코드

#include <stdio.h>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <cmath>
#include <climits>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>
#include <list>
#include <bitset>

using namespace std;

int N, K;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> N >> K;

    const int MAX = 100'001;
    vector<int> dp(MAX, INT_MAX);

    dp[N] = 0;
    queue<int> q;
    q.push(N);

    while (!q.empty())
    {
        int current = q.front();
        q.pop();
        
        //left
        if (current - 1 >= 0)
        {
            if (dp[current - 1] > dp[current] + 1)
            {
                dp[current - 1] = dp[current] + 1;
                q.push(current - 1);
            }
        }

        //right
        if (current + 1 < MAX)
        {
            if (dp[current + 1] > dp[current] + 1)
            {
                dp[current + 1] = dp[current] + 1;
                q.push(current + 1);
            }
        }

        //teleport
        if (current * 2 < MAX)
        {
            if (dp[current * 2] > dp[current])
            {
                dp[current * 2] = dp[current];
                q.push(current * 2);
            }
        }
    }

    cout << dp[K];

    return 0;
}

---