BOJ 13549 숨바꼭질3

백준 13549 링크

https://www.acmicpc.net/problem/13549

풀이

bfs를 쓰면 됩니다. queue보다 deque가 속도가 더 빠른거같네요. 꽤 차이가 납니다.

코드

from collections import deque
input = __import__('sys').stdin.readline
n,m = map(int, input().split())
chaser = [float("inf") for _ in range(100001)]
q = deque([(n,0)])
while q:
    now,moved=q.popleft()
    if chaser[now]>moved:
        chaser[now]=moved
    for i in [now+1,now-1]:
        if 0<=i<=100000 and chaser[i]>moved+1:
            q.append((i,moved+1))
            chaser[i]=moved+1
    if 0<=now*2<=100000 and chaser[now*2]>moved:
            q.append((now*2,moved))
            chaser[now*2]=moved
print(chaser[m])