[백준/python] 13549번 숨바꼭질 3

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

13549번: 숨바꼭질 3

 

문제분석

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 N에 있고, 동생은 K에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 0초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 문제이다.

 

코드

from heapq import *
input = __import__('sys').stdin.readline

n, k = map(int, input().split())
cost = [float('inf')] * (100001)
cost[n] = 0

hq = []
heappush(hq, (0, n))

while hq:
    t, x = heappop(hq)
    if cost[x] != t: continue
    for nx in [(x + 1, 1), (x - 1, 1), (x * 2, 0)]:
        if 0 <= nx[0] < 100001 and cost[nx[0]] > t + nx[1]:
            cost[nx[0]] = t + nx[1]
            heappush(hq, (cost[nx[0]], nx[0]))

print(cost[k])

 

문제풀이

1. 먼저 우선순위 큐인 heapq를 import 해주고, 빠르게 입력받을 수 있도록 input을 설정한다.

2. 수빈이의 위치는 n, 동생의 위치는 k에 저장해준다.

3. 가중치를

cost에 'inf'로 조건 범위에 맞게 만들고, 수빈이의 위치를 cost [n] = 0을 통해서 가중치 0으로 설정한다.

4. 우선순위 큐인 hq를 만들고, 수빈이의 위치 정보(0, n)를 push 해준다.

5. while문을 통해서 다익스트라 알고리즘을 구현한다.

6. 먼저 hq에서 가장 작은 원소를 pop 해서 가중치(=시간)를 t에 위치를 x에 넣어준다.

7. 모든 노드들은 +1, -1, *2의 인접 노드를 가지기 때문에 이를 [(x + 1, 1), (x - 1, 1), (x * 2, 0)]으로 정의해서 for문에 사용한다.

8. if문으로 조건 범위를 설정해둔 후, 가중치를 갱신하고 hq에 추가한다.

9. 마지막으로 노드의 최단 경로 가중치 값을 print 해준다.