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

13549번: 숨바꼭질 3

---

BFS를 사용! 두배한 것은 0초만에 된다는 것이 포인트!

1. 방문 여부 Check 배열과 담을 queue 배열을 생성한다
2. 2배는 0초만에 이루어지므로 먼저 계산되어야하므로 queue 앞으로 넣어준다.
3. +1과 -1 queue 뒤로 넣어준다.

import sys
from collections import deque

input = sys.stdin.readline
N, K = map(int, input().split())
check = [False]*200001
queue = deque([[N, 0]])

def insertque(q, x, c, twice):
    if 0 <= x <=200000 and not check[x]:
        check[x] = True
        if twice:
            q.appendleft([x, c])
        else:
            q.append([x, c])

check[N] = True
answer = 0

while queue:
    pos, cnt = queue.popleft()
    if pos == K:
        answer = cnt
        break
    insertque(queue, 2*pos, cnt, True)
    insertque(queue, pos-1, cnt+1, False)
    insertque(queue, pos+1, cnt+1, False)

print(answer)