[Python]13549. 숨바꼭질 3

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

13549번: 숨바꼭질 3

---

 

이 문제의 경우 가중치가 적용된 BFS 문제로 Deque을 사용해서 해결할 수 있다.

0초로 움직이는 것은 가중치가 0

1초로 움직이는 것들은 가중치가 1

 

따라서 0초일땐 Deque의 앞에다 추가하고

1초일땐 Deque의 뒤에다 추가한다.

 

from collections import deque
 
n, k = map(int, input().split())
MAX = 200000
time = [-1]*(MAX+1)
 
queue = deque()
queue.append(n)
time[n] = 0
 
while queue:
    curr = queue.popleft()
 
    if curr*2 < MAX and time[curr*2] == -1:
            time[curr*2] = time[curr]
            queue.appendleft(curr*2)
 
    if curr-1 >= 0 and time[curr-1] == -1:
        time[curr-1] = time[curr]+1
        queue.append(curr-1)
 
    if curr+1 < MAX and time[curr+1] == -1:
        time[curr+1] = time[curr] + 1
        queue.append(curr+1)
 
    if curr == k:
        print(time[curr])
        break