[백준] 13549번 숨바꼭질 3 파이썬

문제

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

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

입력

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

출력

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

예제 입력 1

5 17

예제 출력 1

2

힌트

수빈이가 5-10-9-18-17 순으로 가면 2초만에 동생을 찾을 수 있다.

제출 답안

• 3가지 경우를 모두 검사하고 해당되면 q에 넣는다.

'''
1. 아이디어
- 3가지 경우를 모두 큐에 넣고
- 동생을 만나면 while문 탈출
2. 시간 복잡도
- ElogV
- E : 2V = 200,000
- logV : log100000 ~= 17
= 3,400,000
3. 변수
- visited []
- dsit []
'''

import sys
from collections import deque
input = sys.stdin.readline
n, k = map(int,input().split())

MAX = 100001
visited = [False] * MAX
dist = [-1] * MAX

q = deque([n])
visited[n] = True
dist[n] = 0
while q:
    now = q.popleft()
    if now == k:
        break
    if (nxt:=now*2) < MAX and not visited[nxt]:
        visited[nxt] = True
        dist[nxt] = dist[now]
        q.appendleft(nxt)
    if (nxt:=now +1) < MAX and not visited[nxt]:
        visited[nxt] = True
        dist[nxt] = dist[now] +1 
        q.append(nxt)
    if 0 <= (nxt:=now - 1) and not visited[nxt]:
        visited[nxt] = True
        dist[nxt] = dist[now] + 1 
        q.append(nxt)

print(dist[k])