[백준] 1697 : 숨바꼭질

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

1697번: 숨바꼭질

---

코드

from collections import deque

N, K = map(int, input().split())
max_position = 100000
position = [0] * (max_position + 1)
dq = deque([N])

while dq:
    pos = dq.popleft()
    if pos == K:
        print(position[K])
        break
    for i in [pos-1, pos+1, 2*pos]:
        if 0 <= i < max_position + 1 and not position[i]:
            position[i] = position[pos] + 1
            dq.append(i)

풀이

 해당 문제는 두 사람이 만날 때 걸리는 '최단 시간'이기 때문에 BFS를 이용하여 풀면 된다.

 가장 애를 먹었던 부분은 정지 조건이다. 처음에는 정지 조건을 position[K] != 0이라는 조건을 사용하였다. 즉, position[K]가 0이 아니게 되면 수빈이가 동생의 위치까지 와서 해당 위치에 최단 시간이 기록되었다는 의미이기 때문이다. 하지만 수빈이와 동생의 위치가 같은 경우(ex. N = 5, K = 5), position[K] == 0임에도 정지해야 하는 반례가 발생한다. 따라서 pos == K라는 정지 조건을 설정해야 한다.

 for문을 살펴보면 수빈이의 경우 1초 후에 1) x-1로 이동, 2) x+1로 이동, 3) 2*x로 순간이동 할 수 있다. 따라서 for문을 돌면서 1) 해당 위치 인덱스가 범위 안에 들어오고, 2) 해당 위치 인덱스에서의 값이 0이라면, 최단 시간을 업데이트 해주면 된다. 이 때 2)번 조건이 중요하다. 만약 해당 위치 인덱스에서 이미 0이 아닌 값이 채워져있다면 당연히 현재 업데이트 해주려는 값보다 작은 값이기 때문에 업데이트 해서는 안된다.