코딩 테스트/Level 3
등산코스 정하기
컴닥
2022. 11. 16. 17:55
반응형
https://school.programmers.co.kr/learn/courses/30/lessons/118669
다익스트라 알고리듬의 변형이다.
from collections import defaultdict
from heapq import heappop, heappush
def solution(n, paths, gates, summits):
summits_set = set(summits)
graph = defaultdict(list)
for i, j, w in paths:
graph[i].append((j, w))
graph[j].append((i, w))
gates_queue = [(0, gate) for gate in gates]
intensities = [float('inf') for _ in range((n + 1))]
for gate in gates:
intensities[gate] = 0
while gates_queue:
intensity, node = heappop(gates_queue)
if node in summits_set or intensity > intensities[node]:
continue
for next_node, weight in graph[node]:
new_intensity = max(intensity, weight)
if new_intensity < intensities[next_node]:
intensities[next_node] = new_intensity
heappush(gates_queue, (new_intensity, next_node))
return min([intensities[summit], summit] for summit in summits)[::-1]
반응형