백준 1697번 숨박꼭질

최단거리문제로 움직일 수 있는 방법이 3가지 있는 경우이다 입력이 숫자 2개라서 새로운 노드를 만들거나 움직임의 수를 저장할 공간이 필요한다

모든 범위의 리스트를 만들어서 각 인덱스에 저장하는 방법도 있지만 이번에는 모든 구간이 필요하다고 생각하지 않았다 (움직일 수 있는 방법이 3가지로 제한되어서) 그래서 딕셔너리를 사용해서 내 위치와 움직인 수를 같이 저장하도록 했다

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

q = deque()
n,k = map(int,input().split())
dic = {n:0} #시작

q.append(n)

while q:
    x = q.popleft()
    if x == k:
        print(dic[x])
        break
    
    for i in (x - 1,x + 1 ,2 * x):

        if i<0 or i>100000: #주어진 범위를 벗어나는 경우
            continue

        if not i in dic: # 딕셔너리에 없는경우 실행 이미 지나갔던 구간이면 실행하지 않고 넘어간다
            dic[i] = dic[x]+1
            q.append(i)