백준 13913 숨바꼭질 4 풀이(c++)

문제 링크

성능 요약

메모리: 3700 KB, 시간: 12 ms

분류

너비 우선 탐색, 그래프 이론, 그래프 탐색

제출 일자

2025년 2월 27일 09:27:24

문제 설명

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 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>
#include <algorithm>

using namespace std;

int N, K;

int visited[100'004] = {0, };
int Parents[100'004] = { -987654321, };


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

    cin >> N >> K;

    visited[N] = 1;
    fill(Parents, Parents + 100'004, -987654321);
    queue<int> q;
    q.push(N);

    while (q.size())
    {
        int iNow = q.front();
        q.pop();
        if (iNow == K)
        {
            break;
        }
        for (int iNext : {iNow + 1, iNow - 1, iNow * 2})
        {
            if (iNext < 0 || iNext >= 100'004)
                continue;
            if (visited[iNext])
                continue;

            visited[iNext] = visited[iNow] + 1;

            Parents[iNext] = iNow;
            q.push(iNext);
        }
    }

    int prev = K;
    cout << visited[K] - 1<<"\n";
    vector<int> v;
    v.push_back(K);
    while (true)
    {
        if (Parents[prev] == -987654321)
            break;
        v.push_back(Parents[prev]);
        prev = Parents[prev];
    }
    
    reverse(v.begin(), v.end());
    for (auto i : v)
        cout << i << " ";

    return 0;
}

 

BFS 를 이용해 풀이 했고 각 값마다 부모(이전) 값을 저장해서 부모가 없을 때 까지 타고 들어가 해당 값을 저장한다음 뒤집어서 풀이했다.

 

스타크래프트 만들때 A* 가 기억났다.