[백준, BOJ] 1697 - 숨바꼭질

1. Question

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

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

1.1 Input

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

1.2 Output

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

1.3 Example

입력	출력
5 17	4

2. Approach

언뜻보면 K를 향해 가능하면 2배씩 하는게 이득일 것 같지만, 사실 중간 중간에 +1, -1을 하는게 더 빠른 경우가 있으며 그 조건을 찾기도 힘들다.

따라서, bfs를 통한 전수조사가 요구되며, 가장 빠른 경로가 나오면 바로 출력하면 된다.

특이점이라면, 일반적인 bfs에서 쓰이는 visited 리스트를 단순 방문 여부말고, level을 의미하게 쓸 수도 있다.

3. Submission

4. Code

import sys
from collections import deque
rl = sys.stdin.readline

N, K = map(int, rl().split())

q = deque([N])
lim = 100001
visited = [0] * lim

def bfs():
    while q:
        cur = q.popleft()
        if cur == K:
            return visited[cur]
        check(cur + 1, cur)
        check(cur - 1, cur)
        check(cur * 2, cur)

def check(next, cur):
    if 0 <= next < lim and (visited[next] == 0 or visited[cur] + 1 < visited[next]):
        visited[next] = visited[cur] + 1
        q.append(next)

print(bfs())