1697 숨바꼭질

백준 1697 숨바꼭질

문제

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

수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

입력

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

출력

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

예제 입력 1


5 17

예제 출력 1

힌트

수빈이가 5-10-9-18-17 순으로 가면 4초만에 동생을 찾을 수 있다.

정답


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

using namespace std;

#define MAX 100001

int N, K, answer;
vector<vector<int>> edge(MAX, vector<int>());
vector<int> parent(MAX);

void Input()
{
    cin >> N >> K;
    for (int i = 0; i < MAX; i++)
    {
        int prevX = i - 1;
        int nextX = i + 1;
        int jumpX = i * 2;
        if (prevX >= 0)
            edge[i].push_back(prevX);
        if (nextX < MAX)
            edge[i].push_back(nextX);
        if (jumpX < MAX)
            edge[i].push_back(jumpX);
    }
}

void Bfs(int here)
{
    queue<int> q;
    vector<bool> visited = vector<bool>(MAX, false);
    visited[here] = true;
    parent.push_back(here);
    q.push(here);

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

        if (here == K)
            break;

        for (int i = 0; i < edge[here].size(); i++)
        {
            int there = edge[here][i];
            if (!visited[there])
            {
                visited[there] = true;
                parent[there] = here;
                q.push(there);
            }
        }
    }
}

void Solution()
{
    Bfs(N);
    int pos = K;
    while (pos != N)
    {
        pos = parent[pos];
        answer++;
    }
}

void Solve()
{
    Input();
    Solution();
    cout << answer << '\n';
}

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

    Solve();
}

해당 코드는 백준 1697번 숨바꼭질 문제를 해결하는 C++ 코드입니다.

코드 리뷰

Input 함수

N과 K를 입력 받습니다.

i에서 갈 수 있는 prevX, nextX, jumpX를 edge[i]에 저장합니다.

Bfs 함수

here부터 시작하여 BFS를 실행합니다.

visited, parent, q 큐를 사용합니다.

here와 연결된 노드들 중 방문하지 않은 노드를 visited에 체크하고 큐에 삽입합니다.

부모 노드를 parent[there] = here로 저장합니다.

K를 찾으면 BFS를 종료합니다.

Solution 함수

Bfs 함수를 실행합니다.

K에서 N으로 돌아가는 경로를 찾습니다.

parent를 이용하여 경로를 추적합니다.

Solve 함수

Input 함수와 Solution 함수를 실행합니다.

정답을 출력합니다.

정답

위 코드는 문제를 해결하는 정답 코드입니다.