[백준] 13549. 숨바꼭질3 (Python)

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

13549번: 숨바꼭질 3

 

💫 걸어서 갈 때보다 순간이동으로 갈 때 시간이 더 적게 걸림 ➡️ appendleft로 먼저 넣어주기

 

from collections import deque

def BFS(start, target):
    q = deque()
    q.append((start, 0)) # start, cnt
    Mincnt = 0
    check = [0]*100001
    while q:
        now, cnt = q.popleft()

        if now == target:
            Mincnt = cnt
            break

        path = [now-1, now+1, now*2]

        for p in path:
            if 0<= p <= 100000 and check[p] == 0:
                check[p] = 1
                if p == now*2:
                    q.appendleft((p, cnt))
                else:
                    q.append((p, cnt+1))

    return Mincnt

n, k = map(int, input().split())

res = BFS(n, k)

print(res)