백준 1697 숨바꼭질 / python

문제 : 1697

풀이 point

bfs를 활용하여 거리를 구할 수 있다. Q는 선입선출 개념이기 때문에 n+1, n-1, $2 \times n$ 경우의 수를 진행하면서 최소 거리를 찾을 수 있다.

1초마다 n+1, n-1, $2 \times n$을 모두 큐에 넣고 진행하기 때문에 모든 경우의 수가 뻗어나가면서 가장 먼저 도착한 값이 최단 시간이 됨을 알 수 있다.

예를들어, n초가 가장 최소일때, n-1이 최소가 될수 없음을 증명해본다. n-1이 최소가 되기 위해서는 그전 값이 큐에 들어가있어야하는데 큐에 들어가있다면 n-1이 최소가 되지 않을 수 없다.(큐에 들어가 있다면 그 큐에 모든 시간 값(가중치)은 동일하기 때문)

범위를 주의해야한다. 동생이 현재 있는 곳을 넘어서서 뒤로(N-1) 올수도 있기 때문

코드

from collections import deque

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

MAX = 100001

dist = [0]*MAX

Q = deque()

Q.append(N)
dist[N]=1

def bfs():
  
  while Q:
    n = Q.popleft()

    if n == K:
      return dist[K]
    
    if n < K and dist[n+1] == 0:
      dist[n+1] = dist[n]+1
      Q.append(n+1)
    if n > 0 and dist[n-1] == 0:
      dist[n-1] = dist[n]+1
      Q.append(n-1)
    if 2*n < MAX and dist[2*n] == 0:
      dist[2*n] = dist[n]+1
      Q.append(2*n)
  
print(bfs()-1)