[백준 / 1697] 숨바꼭질 - Python

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

1697번: 숨바꼭질

 

<풀이>

graph를 만들어서 방문했던 최소 시간을 넣어준다. 해당 시간보다 지금이 더 길다면 건너뛴다.

만야 현재 위치가 k보다 큰 경우 할 수 있는 것은 -1이동밖에 없다. 아닌 경우 -1, +1, *2 이렇게 3가지 경우가 있다.

 

 

 

 

<전체 코드>

from collections import deque

n, k = map(int, input().split())
graph = [float('inf')] * 200000
queue = deque([[n, 0]])
graph[n] = 0

while queue:
    now, time = queue.popleft()
    if graph[now] < time:
        continue
    if now < k:
        nexts = [now-1, now+1, now*2]
    else:
        nexts = [now-1]
    for next in nexts:
        if next == -1:
            continue
        if graph[next] > time+1:
            graph[next] = time+1
            queue.append([next, time+1])

print(graph[k])