[백준 c++] 13913 숨바꼭질 4

문제 설명

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

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

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

• 출력
  첫째 줄에 수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.
  둘째 줄에 어떻게 이동해야 하는지 공백으로 구분해 출력한다.

아이디어

bfs로 탐색할 때 이동경로를 저장하는 벡터를 추가해서 풀었는데 시간초과가 났다. 벡터는 push_back()할 때 지정된 opacity를 초과하면 모든 원소를 삭제하고 벡터 용량을 늘린다음에 다시 그 값을 복사하는 식으로 동작하기 때문이다.

BFS와 함께 배열에 이전 경로 값을 저장하는 식으로 풀 수 있었다. => BFS+trace

• 이전 경로 값을 저장하는 배열 prev
• 현재 위치 here
• 다음 위치 next

BFS의 방문처리와 함께 prev[next]=here
ex) prev[5]=4 : 5의 이전 경로 값은 4

이후에 prev[k]부터 배열을 탐색하여
prev[k] =idx
`prev[idx]=idx

전체 코드

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
using namespace std;
int n, k, r, mx = 100001;
queue<int> q;
int visited[200001];
int pre[200001];

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> k;
    visited[n] = 1;
    q.push(n);
    while (q.size())
    {
        int here = q.front();
        q.pop();
        if (here == k)
        {
            r = visited[k];
            break;
        }
        for (int next : {here + 1, here - 1, here * 2})
        {
            if (next >= mx || next < 0 || visited[next])
                continue;
            visited[next] = visited[here] + 1;
            pre[next] = here;
            q.push(next);
        }
    }
    int idx = k;
    stack<int> s;
    while (idx != n)
    {
        s.push(idx);
        idx = pre[idx];
    }
    s.push(n);
    cout << r - 1 << "\n";
    while (!s.empty())
    {
        cout << s.top() << " ";
        s.pop();
    }
}