[PS] 등산 코스 정하기

문제 링크

코드

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)
        # intensity > intensities[node]: 더 작은 값이 먼저 실행된 경우
        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 결과가 산봉우리에 남아서 편하게 풀 수 있지만 반대로 산봉우리부터 시작해서 어디서부터 시작했는지 또 기록해야 되는 문제가 있었다