링크
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는 정수이다.
출력
수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.
예제 입력 1
5 17예제 출력 1
2힌트
수빈이가 5-10-9-18-17 순으로 가면 2초만에 동생을 찾을 수 있다.
아이디어 스케치
- 수빈이가 동생을 찾는 가장 빠른 시간을 구하는 것이 핵심이다. 따라서 이동시간이 짧은 순간이동이 우선순위가 되어야 한다.
- 우선순위 큐는 FIFO의 구조를 갖는 큐와 달리 우선순위가 높은 데이터가 먼저 나가는 형태의 자료구조로 이 문제를 해결하기에 가장 적합한 자료구조이다.
- 우선순위 큐를 이용하여 이 문제를 해결하면 된다.
코드 분할 설명
n, k = map(int, input().split()) # 수빈이와 동생의 위치를 입력받음
pq = []
heapq.heappush(pq, (0, n)) # 우선순위 큐(pq)를 초기화 -> _item의 첫번째 원소는 우선순위(시간), 두 번째 원소는 시작 노드
visit = [False] * 100001 # 방문여부를 나타내는 visit 리스트를 false로 100001개를 초기화- 수빈이와 동생의 위치를 입력받는다.
- 우선순위 큐(pq)를 초기화한 후 우선순위 큐의 첫번째 원소로 우선순위(시간), 두 번째 원소로는 시작 노드를 큐에 push한다. 이때 수빈이는 아직 이동하지 않았기 때문에 시간은 0으로, 입력 받은 수빈이의 위치(n)가 초기 위치이므로 0과 n을 push한다.
- 방문여부를 나타내는 visit 리스트를 false로 100001개를 초기화한다.
while pq:
time, x = heapq.heappop(pq) # 현재 노드(x)까지 걸린 시간과 현재 노드를 큐에서 꺼냄
visit[x] = True # 현재 노드 방문 체크
if x == k: # 현재 노드가 목표값(k)라면 즉시 종료
print(time)
break
if x - 1 >= 0 and not visit[x - 1]: # x - 1로 이동하는 경우 이동시간(time)을 1 증가시키고 큐에 추가
heapq.heappush(pq, (time + 1, x - 1))
if x + 1 <= 100000 and not visit[x + 1]: # x + 1로 이동하는 경우 이동시간(time)을 1 증가시키고 큐에 추가
heapq.heappush(pq, (time + 1, x + 1))
if x * 2 <= 100000 and not visit[x * 2]: # 2 * x로 이동하는 경우 이동시간(time)을 증가시키지 않고 큐에 추가
heapq.heappush(pq, (time, x * 2))- 루프는 우선순위 큐에 아무 요소도 존재하지 않을 때까지 수행하며 x - 1로 이동하는 경우에는 이동시간이 1초이므로 time + 1과 x - 1위치로 큐에 추가하고, x + 1로 이동하는 경우에는 time + 1과 x + 1위치로 큐에 추가하며, 2x 로 순간이동을 하는 경우에는 이동시간을 증가시키지 않고 2x의 위치로 큐에 추가한다. 단 이동하려는 노드가 정해진 범위내에 존재해야하므로 이동하려는 노드가 정해진 범위 내에 존재하는지 확인하는 조건을 추가해야 한다.
- 위 작업을 수행하면 이동시간이 없는 순간이동이 우선으로 수행, 즉 큐에 제일 앞쪽에 위치하며 좌우로 한 칸씩 이동하는 작업은 순간이동 뒤로 순차적으로 큐에 위치한다. 이동 시간이 없고 이동하는 칸수가 큰 순산이동이 큐에서 먼저 꺼내 지고 한 칸씩 좌우로 이동하는 작업이 큐에서 나중에 꺼내 지기 때문에 최단 시간을 구할 수 있다.
전체코드
import heapq
n, k = map(int, input().split()) # 수빈이와 동생의 위치를 입력받음
pq = []
heapq.heappush(pq, (0, n)) # 우선순위 큐(pq)를 초기화 -> _item의 첫번째 원소는 우선순위(시간), 두 번째 원소는 시작 노드
visit = [False] * 100001 # 방문여부를 나타내는 visit 리스트를 false로 100001개를 초기화
while pq:
time, x = heapq.heappop(pq) # 현재 노드(x)까지 걸린 시간과 현재 노드를 큐에서 꺼냄
visit[x] = True # 현재 노드 방문 체크
if x == k: # 현재 노드가 목표값(k)라면 즉시 종료
print(time)
break
if x - 1 >= 0 and not visit[x - 1]: # x - 1로 이동하는 경우 이동시간(time)을 1 증가시키고 큐에 추가
heapq.heappush(pq, (time + 1, x - 1))
if x + 1 <= 100000 and not visit[x + 1]: # x + 1로 이동하는 경우 이동시간(time)을 1 증가시키고 큐에 추가
heapq.heappush(pq, (time + 1, x + 1))
if x * 2 <= 100000 and not visit[x * 2]: # 2 * x로 이동하는 경우 이동시간(time)을 증가시키지 않고 큐에 추가
heapq.heappush(pq, (time, x * 2))제출 결과
IT Velog