[백준] 13913번: 숨바꼭질 4 (C++)

13913번: 숨바꼭질 4

---

문제)

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

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

 

 

 

입력 :

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

 

 

 

 

출력 :

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

둘째 줄에 어떻게 이동해야 하는지 공백으로 구분해 출력한다.

 

 

 

 

 

풀이)

 

#include <iostream>
#include <vector>
#include <queue>
 
using namespace std;
 
int n, k;
// 방문 배열
int visited[200100];
 
void bfs()
{
    // queue 안에 앞으로 갈 위치와 나의 이동 과정을 기록한다
    queue<pair<int, vector<int>>> q;
    visited[n] = 1;
    q.push(make_pair(n, vector<int>(1, n)));
 
    while (!q.empty())
    {
        int a = q.front().first;
        vector<int> temp = q.front().second;
        q.pop();
 
        // 목적지에 도착했을 경우.
        if (a == k)
        {
            cout << visited[a] - 1 << endl;
            for (auto next : temp)
            {
                cout << next << " ";
            }
            return;
        }
 
        for (auto next : { a + 1, a - 1, a * 2 })
        {
            if (0 > next || next > 200100) continue;
            if (visited[next]) continue;
 
            visited[next] = visited[a] + 1;
            temp.push_back(next);
            q.push(make_pair(next, temp));
            // 한 vector를 가지고 활용하기 때문에 pop을 해줘야 한다.
            temp.pop_back();
        }
    }
 
 
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
 
    cin >> n >> k;
 
    if (n < k)
    {
        bfs();
    }
    else if (n > k)
    {    // n이 큰 경우에는 작아지는 방법이 -1 밖에 없으므로, 
        // 예외처리를 해줘야 한다.
        cout << n - k << endl;
        for (int i = n; i >= k; i--)
        {
            cout << i << " ";
        }
    }
    else if (n == k)
    {    // n > k와 마찬가지로 n == k도 예외처리를 해줘야한다.
        cout << 0 << endl;
        cout << n;
    }
 
    return 0;
}

 

 

---

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

13913번: 숨바꼭질 4