# 1697 숨바꼭질

www.acmicpc.net/problem/1697

1697번: 숨바꼭질

from collections import deque 

n, k = map(int,input().split())
t = [0]*100001

def bfs():
  q = deque()
  q.append(n)

  while q:
    a = q.popleft()

    if a == k : 
      print( t[k])
      return 
    
    for b in ( a-1, a+1, a*2):
      if 0<= b < 100001 and not t[b]:
        t[b] = t[a] +1
        q.append(b)

bfs()

 

n부터 시작 -> 이동 가능한 칸으로 이동 -> 그 칸에서 다시 센다 

한 번 처리된 곳은 또 가지 않는다. 

생각해보면 처음 나왔을 때의 값보다 작은 값이 들어오지 않는다. 

 

+) 이걸 dfs 로 접근하면 무한 loop가 나온다.