백준 13549 숨바꼭질 3(python)

문제

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

13549번: 숨바꼭질 3

---

주어진 2가지 경우로 이동하면서 목표지점으로 가는 문제였습니다. 이렇게 간선의 가중치가 두 종류로만 이루어진 문제를 0,1 BFS라고 부르며 데크를 사용하여 구현할 수 있습니다. 구현 과정은 다음과 같습니다.

• 처음 시작지점을 데크에 넣어줍니다.
• 데크의 가장 앞쪽 값을 pop 해 주어서 갈 수 있는 조건에 따라 시간을 구해 줍니다.
• x-1, x+1 일때는 1초의 시간을 증가시켜 데크의 뒤쪽에 넣어주고,  2*x인 경우에는 시간이 걸리지 않으므로 데크의 앞쪽에 먼저 넣어줍니다.
• 최종적으로 도착지점 K에 도달하면 걸린 시간을 출력해 줍니다.

---

소스코드 

from collections import deque
import sys
input = sys.stdin.readline


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

MAX = 100001
ch = [0] * MAX
q = deque()
q.append((N, 0))

while q:
    tmp = q.popleft()
    if tmp[0] == K:
        print(tmp[1])
        break
    for next in [tmp[0]-1, tmp[0]+1, 2*tmp[0]]:
        if 0 <= next < MAX and ch[next] == 0:
            ch[next] = 1
            if next == tmp[0]-1 or next == tmp[0]+1:  # x+1,x-1 로 한칸 가는 경우
                q.append((next, tmp[1]+1))
            if next == tmp[0]*2:  # 2*x 만큼 가는경우
                q.appendleft((next, tmp[1]))  # 데크의 앞에 넣어준다