백준 알고리즘 1697번 : 숨바꼭질

Zoo Da·2021년 7월 7일

백준 알고리즘 재풀이예정!

백준 알고리즘

목록 보기

98/337

링크

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

문제

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

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

입력

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

출력

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

예제 입력 및 출력, 힌트

풀이 코드(C++)

// 1697번 : 숨바꼭질(실버 1)

#include <iostream>
#include <queue>
#include <algorithm>
#include <vector>
#include <cstring>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define MAX 100001

using namespace std;

int dist[MAX];
int n, k;

int main()
{
    fastio;
    cin >> n >> k;
    memset(dist, -1, sizeof(dist)); // 모든 거리를 -1로 초기화 시킨다
    queue<int> Q;
    dist[n] = 0;
    Q.push(n);
    while (!Q.empty())
    {
        int cur = Q.front(); // 현재 큐에 있는 좌표
        Q.pop();
        for (int i : {cur + 1, cur - 1, 2 * cur})
        {
            if (i < 0 || i > MAX - 1)
            {
                continue;
            }
            if (dist[i] != -1)
                continue;
            dist[i] = dist[cur] + 1;
            Q.push(i);
            if (i == k)
                break;
        }
    }
    cout << dist[k];
    return 0;
}