백준 : 13913번 숨바꼭질 4 BFS(c++)

백준 링크

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

13913번: 숨바꼭질 4

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
2 초	512 MB	36900	12396	8729	31.405%

문제

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

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

입력

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

출력

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

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

예제 입력 1

5 17

예제 출력 1

4
5 10 9 18 17

예제 입력 2

5 17

예제 출력 2

4
5 4 8 16 17

코드 풀이

어제 포스팅한 문제와 비슷한 문제인데 다른부분은 경로를 출력하는것입니다.

기본적인 코드는 BFS탐색을 진행하여 최종 K까지의 위치를 구하는 방식은 동일한데

루트를 저장할 배열을 만들어 경로를 저장할 수 있도록 해주었습니다.

BFS탐색 while문이 끝나게되면 Prev에 저장된 루트 위치를 탐색해서 경로를 스택에 저장하고 경로를 저장한 스택을 순서대로 출력하여 최종 경로를 뽑아내면 됩니다.

 

BFS탐색이 끝나고 Prev배열을 확인해보면

Index	5	6	7	8	9	10	11	12	13
Value	0	5	6	4	10	5	10	6	12

Index	14	15	16	17	18	19	20
Value	7	14	8	18	9	20	10

가 나오는것을 확인할 수 있는데

K 즉, 17의 인덱스의 값(루트)는 18이 되고 -> 18의 루트는 9  -> 9의 루트는 10 -> 10의 루트는 5가되어

최종 경로는 뒤에서부터 5 -> 10 -> 9 -> 18 -> 17이 됩니다.

코드

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>

using namespace std;


int main()
{
    int N, K;

    cin >> N >> K;

    bool Visited[100001] = {};
    int Dist[100001] = {};
    // 부모를 저장하기 위한 배열
    int Prev[100001] = {};

    queue<int> q;

    q.push(N);
    Visited[N] = true;

    while (!q.empty())
    {
        int Current = q.front();
        q.pop();

        if (Current == K)
            break;

        if (Current * 2 <= 100000 && !Visited[Current * 2])
        {
            q.push(Current * 2);
            Visited[Current * 2] = true;
            Dist[Current * 2] = Dist[Current] + 1;
            // 부모인 Current를 값으로 넣어준다.
            Prev[Current * 2] = Current;
        }
        if (Current + 1 <= 100000 && !Visited[Current + 1])
        {
            q.push(Current + 1);
            Visited[Current + 1] = true;
            Dist[Current + 1] = Dist[Current] + 1;
            // 부모인 Current를 값으로 넣어준다.
            Prev[Current + 1] = Current;
        }
        if (Current - 1 >= 0 && !Visited[Current - 1])
        {
            q.push(Current - 1);
            Visited[Current - 1] = true;
            Dist[Current - 1] = Dist[Current] + 1;
            // 부모인 Current를 값으로 넣어준다.
            Prev[Current - 1] = Current;
        }
    }

    cout << Dist[K] << '\n';

    // i가 인덱스가 되고 해당 값이 루트가된다.
    stack<int> path;
    for (int i = K; i != N; i = Prev[i]) 
    {
        path.push(i);
    }
    path.push(N);

    while (!path.empty())
    {
        cout << path.top() << " ";
        path.pop();
    }
    cout << endl;

    return 0;
}