[백준] 1697: 숨바꼭질 python 구현 / BFS

문제

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

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

풀이

1. n과 k의 범위를 제한하여 음수 or 큰 수에 대한 필요 없는 탐색은 진행하지 않을 것
2. n==k 일 경우를 대비할 것
3. vst를 사용하여 한 번 탐색한 곳은 다시 탐색하지 않을 것

CODE

from collections import deque

n, k = map(int, input().split())
vst = [0] * 1000000
def bfs(cx, ctime):
    queue = deque()
    queue.append((cx, ctime))

    dx = [1, -1, 2]

    while queue:
        x, time = queue.popleft()

        for i in dx:
            if i == 1:
                nx = x + 1
            elif i == -1:
                nx = x - 1
            else:
                nx = x * 2
            if nx < 0 or nx > 100000 : continue # 범위 제한
            if vst[nx]: continue # 탐색했던 곳은 재탐색 x
            if nx == k:
                return time + 1
            vst[nx] = 1
            queue.append((nx, time+1))

print(0 if n==k else bfs(n, 0))

코드를 작성하는 것은 문제가 없는데,, 반례에 대한 생각이 짧은 것 같다. ㅠ