백준 1697번 - 숨바꼭질

백준 1697번 - 숨바꼭질

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가 주어진다.

출력

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

접근

• BFS와 삼분탐색을 활용하여 푼다.

• 현재 위치(x)에서 이동할 수 있는 방법은 x*2, x+1, x-1 세 가지이다.

• 현재 위치가 목표 위치에 도달했을 때의 cnt값이 정답.

C++ Code

#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;
​
int find(int from, int to)
{
    queue<pair<int, int>> q;
    bool visited[100001] = { false };
    q.push({ from, 0 });
​
    while (!q.empty()) {
        int cur = q.front().first;
        int cnt = q.front().second;
        q.pop();
​
        if (cur < 0 || cur > 100000) continue;
        if (visited[cur]) continue;
​
        visited[cur] = true;
​
        if (cur == to)
            return cnt;
​
        q.push({ cur * 2, cnt + 1 });
        q.push({ cur + 1, cnt + 1 });
        q.push({ cur - 1, cnt + 1 });
    }
}
​
int main(void) {
    int n, k;
    scanf("%d %d", &n, &k); 
    printf("%d\n", find(n, k));
    return 0;
}
​