[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는 정수이다.

• 출력

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

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

• 예제 입력

5 17

5 17

• 예제 출력

4
5 10 9 18 17

4
5 4 8 16 17

• 접근방식

이전 문제(12851번 숨바꼭질 2) N에서 K 까지의 최단거리를 구하는 그래프를 그리고 방문한 정점을 표시, 최단거리는 BFS를 사용하고 방문한 정점은 previsited라는 곳에 저장

BFS 하면서 방문한 정점 저장

저장한 정점은 따로 벡터에 넣는데 반대 방향이라 reverse필요

• 코드

#include <iostream>
#include <queue>
#include <algorithm>

using namespace std;

const int MAX = 100004;
int visited[MAX + 4], previsited[MAX + 4];
int n, k, result;
vector<int> v;
queue<int> q;
int main()
{
    int n, k;
    cin >> n >> k;

    visited[n] = 1;
    q.push(n);
    while (q.size())
    {
        int here = q.front();
        q.pop();
        if (here == k)
        {
            result = visited[k];
            break;
        }
        for (int next : {here + 1, here - 1, here * 2})
        {
            if (next >= MAX || next < 0 || visited[next])    continue;
            visited[next] = visited[here] + 1;
            previsited[next] = here;
            q.push(next);
        }
    }
    for (int i = k; i != n; i = previsited[i])
    {
        v.push_back(i);
    }
    v.push_back(n);
    reverse(v.begin(), v.end());

    cout << result - 1 << '\n';

    for (int i : v)
    {
        cout << i << ' ';
    }

    return 0;
}

 

• 문제링크 : https://www.acmicpc.net/problem/13913

13913번: 숨바꼭질 4