[BFS] 숨바꼭질

기억하자. 가중치가 없는 최단 경로는 무조건 BFS

가중치가 있는 경우 다익스트라

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

1697번: 숨바꼭질

 

여느 BFS 문제와 크게 다르지 않았음

from collections import deque

N, K = [int(x) for x in input().split()]

#M = max(N,K) ## 이걸로 하면 안되고 걍 100000 사용하자
visited = {i:0 for i in range(100000)}

queue = deque()
queue.append(N)
visited[N] = 0

while queue :
    current = queue.popleft()
    if current == K :
        break
        
    moving = [current+1,current-1,2*current,(-2)*current]
    for i in range(4) :
        new = moving[i]

        if new < 0 or new > 100000 :
            continue

        if visited[new] == 0 :
            queue.append(new)
            visited[new] = visited[current] + 1
            
print(visited[K])