백준 1697번 파이썬

from collections import deque
def bfs(n,k):
    q = deque()
    q.append((n, 0))
    visited =[0] * 100001
    visited[n] = 1
    while 1:
        x , t = q.popleft()       
        if x == k:
            print(t)
            break
        else:
            if (x+1) < 100001 and visited[x+1] == 0:
                q.append((x+1, t+1))
                visited[x+1] =1
            if (x-1) >= 0 and visited[x-1] == 0 :
                q.append((x-1, t+1))
                visited[x-1] = 1
            if 0 < 2*x < 100001 and visited[2*x] == 0 :           
                q.append((2*x, t+1))
                visited[2*x] = 1


N, K = map(int, input().split())
bfs(N, K)

시간복잡도: O(n)