[백준 13549] 숨바꼭질 3

 

 

문제

---

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

13549번: 숨바꼭질 3

 

 

나의 풀이

---

우선순위큐를 사용해서 풀면 된다. 큐에 삽입할 때는 시간이 빠른 순서로 정렬될 수 있도록 (시간, 위치)의 순서쌍을 넣어준다. 주의할 점은 삽입하는 순서인데, x 위치에서 가능한 총 경우의 수는 x-1, x+1, 2x의 세 가지이다. 이 때 순간이동을 하는 경우 소요되는 시간이 0초로 가장 짧으므로, 2x의 위치를 먼저 삽입한 뒤에 방문검사를 해서 x-1, x+1을 넣어주어야 한다.

가령, 1에서 2로 가는 경우 2x를 먼저 방문하면 0초가 소요되지만 x+1을 먼저 방문하면 1초가 되어 결과값이 최소가 아니게 된다.

 

코드

---

# https://www.acmicpc.net/problem/13549
import heapq

N, K = map(int, input().split())
visit = [0]*100001
hq = []
heapq.heappush(hq, (0,N))
visit[N] = 1
while hq:
    t, pos = heapq.heappop(hq)
    if pos == K:
        print(t)
        break
    if 0<=2*pos<=100000 and visit[2*pos] == 0:
        heapq.heappush(hq, (t, 2*pos))
        visit[2*pos] = 1
    if 0<=pos-1<=100000 and visit[pos-1] == 0:
        heapq.heappush(hq, (t+1,pos-1))
        visit[pos-1] = 1
    if 0<=pos+1<=100000 and visit[pos+1] == 0:
        heapq.heappush(hq, (t+1,pos+1))
        visit[pos+1] = 1