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

13913 숨바꼭질4 골드 4

문제

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

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

입력

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

출력

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

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

풀이

• 이전 숨바꼭질과 같이 BFS를 사용하는데 정답까지의 경로를 알아야 한다.
• 경로를 저장하기 위해 parent배열을 만들어 queue에 입력될때마다 parent정보를 입력해준다.
• 목적지에 도착하면 parent를 따라가며 출력한다.
• 메모리 초과가 났는데 살펴보니 visited배열에 위치 int를 저장하고 있었다.(실수)
• 이런 실수 안하게 애초에 visited는 bool로 선언하자.

코드

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;

bool visited[100001];
int n, k;
int parent[100001];
queue<pair<int, int> > q;
vector<int> fast;

void bfs(int start)
{
    visited[start] = true;
    q.push(make_pair(start, 0));

    while(!q.empty())
    {
        int pos = q.front().first;
        int sec = q.front().second;
        q.pop();
        // cout << pos << endl;
        if(pos == k){
            cout << sec << endl;
            while(pos != n)
            {
                fast.push_back(pos);
                pos = parent[pos];
            }
            fast.push_back(n);
            reverse(fast.begin(), fast.end());
            for(int i = 0; i < fast.size(); i++)
            {
                cout << fast[i] << " ";
            }
            break;
        }

        if(pos - 1 >= 0 && pos - 1 <= 100000 && visited[pos - 1] == 0)
        {
            q.push(make_pair(pos - 1, sec + 1));
            parent[pos - 1] = pos;
            visited[pos -1] = true;
        }
        if(pos + 1 >= 0 && pos + 1 <= 100000 && visited[pos + 1] == 0)
        {
            q.push(make_pair(pos + 1, sec + 1));
            parent[pos + 1] = pos;
            visited[pos + 1] = true;
        }
        if(pos * 2 >= 0 && pos * 2 <= 100000 && visited[pos * 2] == 0)
        {
            q.push(make_pair(pos * 2, sec + 1));
            parent[pos * 2] = pos;
            visited[pos * 2] = true;
        }
    }
}

int main()
{
    cin >> n >> k;

    bfs(n);

    return 0;
}

• ps
• bfs