[Baekjoon] 1697: 숨바꼭질 - (C3, S1) BFS

문제
수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

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

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

1697번: 숨바꼭질

 

가장 빠른 시간을 구해야 하므로 BFS를 이용하여 수빈이의 위치가 동생의 위치가 되면 종료하고 걸린 시간을 출력한다. 사실상 최단 거리를 찾는 알고리즘과 동일하다. 

#include <iostream>
#include <vector>
#include <queue>
#define MAX_POS 100000
using namespace std;

void bfs(int v, int u, vector<bool> &visited, vector<int> &time)
{
    queue<int> q;
    visited[v] = true;
    time[v] = 0;
    q.push(v);

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

        int dx[3] = {cur - 1, cur + 1, 2 * cur};
        for (int i = 0; i < 3; i++)
        {
            int nx = dx[i];

            if (nx >= 0 && nx <= MAX_POS && !visited[nx])
            {
                time[nx] = time[cur] + 1;
                if (nx == u)
                {
                    cout << time[nx];
                    return;
                }
                visited[nx] = true;
                q.push(nx);
            }
        }
    }
}

time[nx]는 시작접 v로부터 nx까지 이동하는데 누적 시간이 된다. 

 

int main()
{
    // freopen("input.txt", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, K;
    cin >> N >> K;

    if (N == K)
    {
        cout << 0;
        return 0;
    }
    vector<bool> visited(MAX_POS + 1, false);
    vector<int> time(MAX_POS + 1, 0);

    bfs(N, K, visited, time);
    return 0;
}

N == K 일 때의 예외처리만 잘 해주면 된다.