이 문제는 heap 자료 구조를 이용한 다익스트라(Dijkstra) 알고리즘을 이용해 푸는 문제이다.
heap을 사용하지 않고 구현하면, 매번 최단 거리가 가장 짧은 노드를 선형 탐색해야 하고, 현재 노드와 연결된 노드를 매번 일일이 확인해야 한다.
출발지에서 산봉우리를 도착할 때의 최소 intensity 값을 구하면 똑같은 경로로 출발지까지 다시 이동하면 되기 때문에 편도 경로만 고려하면 된다.
출발지(출입구)들을 heap에 push 해주고 방문 기록을 해준다.
defaultdict(list) 형태 안에 연결된 노드와 가중치를 입력한다.
gates, summits를 해쉬화 하여 시간복잡도를 줄인다.(O(N) -> O(1))
heap 안에 아무것도 없을 때까지 반복
4-1. 현재 노드가 산봉우리거나 intensity가 기록된 intensity보다 더 클 경우 continue
4-2. 다음 노드의 intensity가 기록된 intensity보다 작을 경우 기록하고, heap에 push 한다.
기록한 노드에 따른 intensity를 바탕으로 intensity가 가장 작은 이동경로(출구)를 찾는다.
from collections import defaultdict
from heapq import heappush, heappop
def solution(n, paths, gates, summits):
def get_min():
hq = []
visited = [10000001] * (n+1)
set_gates = set(gates) # 문제 풀이 3번
for gate in set_gates: # 문제 풀이 1번
heappush(hq, (0, gate))
visited[gate] = 0
while hq: # 문제 풀이 4번
intensity, node = heappop(hq)
# 산봉우리거나 intensity가 더 클 경우
# 문제 풀이 4-1번.
if node in set_summit or intensity > visited[node]: continue
# 문제 풀이 4-2번
for weight, next_node in graph[node]:
next_intensity = max(weight, intensity)
if next_intensity < visited[next_node]:
visited[next_node] = next_intensity
heappush(hq, (next_intensity, next_node))
min_intensity = [0, 10000001]
for summit in summits: # 문제 풀이 5번
if min_intensity[1] > visited[summit]:
min_intensity[0] = summit
min_intensity[1] = visited[summit]
return min_intensity
summits.sort()
# 문제 풀이 3번
set_summit = set(summits) #sumiits 해쉬화하여 시간복잡도 줄임
graph = defaultdict(list)
# 문제 풀이 2번
for i,j,w in paths:
graph[i].append((w,j))
graph[j].append((w,i))
return get_min()