숨바꼭질3

❓문제

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

❗문제 정리

📑코드

import heapq

n, k=map(int, input().split())
INF=int(1e9)
distance=[INF]*(100001)#최대 100000

def heap_dijkstra(start):
	q=[]
	heapq.heappush(q,(0,start))
	distance[start]=0
	
	while q:
	    dist, now=heapq.heappop(q)
	    for i in [now+1, now-1, now*2]:#가능한 경우의수가 그래프가 됨.
	        if 0 <= i <= 100000 and distance[i]==INF:
	            if i==now*2:
	                distance[i]=dist
	                heapq.heappush(q,(dist,i))
	            else:
	                distance[i]=dist+1
	                heapq.heappush(q,(dist+1,i))
heap_dijkstra(n)
print(distance[k])

📝코드 설명

1. 힙큐라이브러리 임포트, 필요한 인수 받기, 최단거리(시간) 테이블 만들기

import heapq

n, k=map(int, input().split())
INF=int(1e9)
distance=[INF]*(100001)#최대 100000

거리를 시간으로 간주한다.
최단거리(시간) 테이블의 크기를 노드의 최대수+1만큼의 크기로 지정한다.
n(int) : 시작위치 , k(int) : 도착위치

2. 다익스트라 알고리즘

def heap_dijkstra(start):
	q=[]
	heapq.heappush(q,(0,start))
	distance[start]=0
	
	while q:
	    dist, now=heapq.heappop(q)
	    for i in [now+1, now-1, now*2]:#가능한 경우의수가 그래프가 됨.
	        if 0 <= i <= 100000 and distance[i]==INF:
	            if i==now*2:
	                distance[i]=dist
	                heapq.heappush(q,(dist,i))
	            else:
	                distance[i]=dist+1
	                heapq.heappush(q,(dist+1,i))

기존의 다익스트라와 동일하나, graph가 아닌 현재노드 now에서 수빈이가 움직일 수 있는 경우의 수([now-1, now+1, 2now])를 넣는다.
0≤노드수≤100,000 이라는 문제에 따라, 움직일 수 있는 노드의 위치를 (0,100,000)으로 제한한다. 그리고 최단거리 테이블이 아직 업데이트 되지 않았을때만을 골라 시간초과를 방지한다.

• 현재 위치에서 2배인 위치로 가는 경우 시간은 0초가 흐르기에, 기존의 소요시간인 dist를 그대로 출력한다.
• 현재 위치에서 1칸씩 움직이는 경우 시간 1초를 더해준다.

3. 실행 후 출력

heap_dijkstra(n)
print(distance[k])

distance일부분

🎖제출 결과

💡insight

접근방식을 모르겠어서 서치한 결과, 갈 수 있는 경우의 수를 기존 다익스트라에서 사용하는 graph라 생각하면된다는 답을 얻음.