문제

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

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

입력

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

출력

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

---

풀이방법

• 시작 위치를 1로 저장, 이동 시 0인 경우만 추가 이동
• 순간이동의 경우, 다른 경우와 다르게 0초가 걸리기 때문에 제일 먼저 확인
  동생이 없다면 큐 맨 앞에 위치 추가 후 이동 전 위치의 시간과 동일하게 저장
• 그 외의 경우, 이동한 위치에 동생이 없다면 큐 맨 뒤에 위치 추가 후(이동 전 위치의 시간 + 1) 저장
• 동생을 만나면 (동생 위치의 시간 - 1) 출력 (시작 위치가 1로 시작했기 때문)

Code

from collections import deque

MAX_VALUE = 100000

n, k = map(int, input().split())
queue = deque()
visited = [0 for _ in range(MAX_VALUE+1)]
queue.append(n)
visited[n] = 1

while queue:
    x = queue.popleft()
    if x*2 <= MAX_VALUE and visited[x*2] == 0:
        queue.appendleft(x*2)
        visited[x*2] = visited[x]
    if x == k or 2*x == k:
        print(visited[k] - 1)
        break
    if x - 1 >= 0 and visited[x-1] == 0:
        queue.append(x-1)
        visited[x-1] = visited[x] + 1
    if x + 1 <= MAX_VALUE and visited[x+1] == 0:
        queue.append(x+1)
        visited[x+1] = visited[x] + 1

아쉬운 점

x-1보다 x+1을 먼저 이동하게 되는 경우 틀림
이 부분 추가로 공부 필요함