문제 링크
코드
from heapq import heappush, heappop
MAX = 987654321
def solution(n, paths, gates, summits):
graph = {x: [] for x in range(1, n + 1)}
for s, d, w in paths:
graph[s].append((d, w))
graph[d].append((s, w))
summits = set(summits)
intensities = [MAX] * (n + 1)
pq = []
for gate in gates:
heappush(pq, (gate, 0))
intensities[gate] = 0
while pq:
node, intensity = heappop(pq)
if (node in summits) or (intensity > intensities[node]):
continue
for d, w in graph[node]:
new_intensity = max(intensity, w)
if intensities[d] > new_intensity:
intensities[d] = new_intensity
heappush(pq, (d, new_intensity))
return min(map(lambda x: [x, intensities[x]], summits), key = lambda x: (x[1], x[0]))
문제 해설
참고 블로그
리뷰
- 변형된 다익스트라 알고리즘을 사용하면 풀 수 있을 것이라는 생각은 했지만 heap을 이용하지 않으면 시간 초과가 났다. 다익스트라 알고리즘에 대해 복습이 필요할 것 같다
- 산봉우리의 값만이 중요하기 때문에 입구부터 시작하면 intesity 결과가 산봉우리에 남아서 편하게 풀 수 있지만 반대로 산봉우리부터 시작해서 어디서부터 시작했는지 또 기록해야 되는 문제가 있었다