백준 13913 - 숨바꼭질 4

문제 설명

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

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

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

---

 

 

 

 

 

 

제한 사항

---

 

 

 

 

 

 

풀이

문제를 요약하면, +1, -1, *2를 이용하여 N부터 K까지 도착하는 최소 이동 횟수와 경로를 출력하는 것이다.

BFS 혹은 DFS로 간단하게 문제를 풀 수 있다.

하지만, DFS로 경로를 유지하는 것이 불편하고 메모리가 충분히 크기 때문에 BFS로 경로를 담은 배열을 유지하도록 구현하였다.

또한, DFS는 0 이하, 100,000 이상의 범위까지 계속하여 탐색하는 과정이 필요하지만 BFS는 K를 발견하면 종료할 수 있기 때문에 좀 더 효율적이라 생각한다.

 

BFS과정은 간단하다.

현재 수에 +1, -1, *2를 계산한 뒤, 최소 이동 횟수를 갱신한다.

만약, 이미 기록되어 있다면 기록된 것보다 더 빨리 도착하는 것은 불가능하기 때문에 무시한다.

+1을 처리하는 코드는 다음과 같다.

queue<pair<int, vector<int>>> q;
q.push({ N, {N} });
while (!q.empty())
{
    auto [current, log] = q.front();
    q.pop();

    if (current + 1 < MAX)
    {
        if (dp[current + 1] == INT_MAX)
        {
            dp[current + 1] = dp[current] + 1;
            log.push_back(current + 1);
            q.push({ current + 1, log });

            if (current + 1 == K)
            {
                cout << dp[current + 1] << "\n";
                for (auto num : log)
                {
                    cout << num << " ";
                }

                return 0;
            }

            log.pop_back();
        }
    }
    
    ...
}

---

 

 

 

 

 

전체 코드

#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>

using namespace std;

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


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

    cin >> N >> K;
    
    if (N == K)
    {
        cout << 0 << "\n";
        cout << N;
        return 0;
    }

    dp[N] = 0;
    queue<pair<int, vector<int>>> q;
    q.push({ N, {N} });
    while (!q.empty())
    {
        auto [current, log] = q.front();
        q.pop();

        if (current + 1 < MAX)
        {
            if (dp[current + 1] == INT_MAX)
            {
                dp[current + 1] = dp[current] + 1;
                log.push_back(current + 1);
                q.push({ current + 1, log });

                if (current + 1 == K)
                {
                    cout << dp[current + 1] << "\n";
                    for (auto num : log)
                    {
                        cout << num << " ";
                    }

                    return 0;
                }

                log.pop_back();
            }
        }

        if (current - 1 >= 0)
        {
            if (dp[current - 1] == INT_MAX)
            {
                dp[current - 1] = dp[current] + 1;
                log.push_back(current - 1);
                q.push({ current - 1, log });

                if (current - 1 == K)
                {
                    cout << dp[current - 1] << "\n";
                    for (auto num : log)
                    {
                        cout << num << " ";
                    }

                    return 0;
                }

                log.pop_back();
            }
        }
            
        if (current * 2 < MAX)
        {
            if (dp[current * 2] == INT_MAX)
            {
                dp[current * 2] = dp[current] + 1;
                log.push_back(current * 2);
                q.push({ current * 2, log });

                if (current * 2 == K)
                {
                    cout << dp[current * 2] << "\n";
                    for (auto num : log)
                    {
                        cout << num << " ";
                    }

                    return 0;
                }

                log.pop_back();
            }
        }
    }

    return 0;
}

---