[BAEKJOON]백준 13549번 숨바꼭질3 - 그래프(Graph), BFS(너비우선탐색), Deque(덱 자료구조)

백준 13549번 숨바꼭질3

백준 13549번 숨바꼭질3

bfs 다익스트라로 최소 거리를 계산함. 순간이동은 비용 0이라서 데크 appendleft()로 맨 앞에다 넣어줘야함.

코드

import sys
import collections
input = sys.stdin.readline

N, K = map(int, input().split())
Q = collections.deque([(N, 0)])
visited = [False]*100001
while Q:
    loc, count = Q.popleft()
    if loc == K:
        print(count)
        break
    if not visited[loc]:
        visited[loc] = True
        if 0<= (2*loc) <= 100000:
            # 순간이동 비용 0이라서 appendleft()
            Q.appendleft((2*loc, count))
        if 0<= (loc+1) <= 100000:
            Q.append((loc+1, count+1))
        if 0<= (loc-1) <= 100000:
            Q.append((loc-1, count+1))