[문제 바로가기] https://www.acmicpc.net/problem/13549
📌문제 설명
수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 0초 후에 2*X의 위치로 이동하게 된다.
수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.
입력
첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.출력
수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.
💡 문제 풀이
heapq를 이용한 BFS로 문제를 해결하였다.
가장 빠른 시간을 찾을 때 관건은 순간이동이다. (순간이동은 0초가 걸리기 때문!)
3가지 경우(x-1, x+1, x*2)에 대해서 이동했을 때 시간과 위치를 계산하여 우선순위큐(heapq)에 넣는다.
이 때, 우선순위는 당연히 '시간'이다. (시간, 위치)형태로 우선순위큐(heapq)에 넣으면 시간을 기준으로 최소힙 자료구조를 만든다.
- (시간, 위치)형태로 우선순위큐에 넣었기 때문에 순간이동부터 실행된다.
- 순간이동은 소요 시간이 0이기 때문에 x*2에 해당하는 위치는 모두 시간이 0이게 된다.
- x*2에 해당하는 위치가 아닌 경우(=아직 이동하지 않은 위치)는 x+1, x-1로 이동해야 한다.
→ 이전 이동시간+1을 해주어 갱신한다.
탐색을 하면서 해당 위치에 초기값(int(1e9)이 아닌 이동거리값으로 최신화되면 그 값을 return 한다.
코드는 다음과 같다.
import sys, heapq
N, K = map(int, input().split())
check = [int(1e9)] * 100001
check[N] = 0
heap = []
heapq.heappush(heap, (0, N))
while heap:
move, idx = heapq.heappop(heap)
if check[K] != int(1e9):
break
for value in [idx*2, idx-1, idx+1]:
if 0 <= value < 100001:
if check[value] == int(1e9) and idx*2 == value:
heapq.heappush(heap, (move, value))
check[value] = move
elif check[value] == int(1e9):
heapq.heappush(heap, (move+1, value))
check[value] = move+1
print(check[K])
허브