[프로그래머스] 등산코스 정하기 (파이썬)

난이도 : LEVEL 3

문제링크 : https://school.programmers.co.kr/learn/courses/30/lessons/118669

문제해결 아이디어

• 문제에서는 출입구 -> 산봉우리 -> 출입구까지 이동경로를 요구하지만

• 출입구 -> 산봉우리까지 최솟값을 구한다면 내려올때는 같은 경로로 내려오면 되기때문에 편도만 구한다.

• 일반적인 다익스트라 문제는 가중치의 합을 비교하는 데 이 문제는 지나온 경로중 가장 큰 가중치를 비교하는 케이스였다.

• distance 배열에는 각 노드 까지 가는데 필요한 가장 큰 가중치를 저장한다.

• 힙에 현재까지의 가장 큰 가중치, 현재 노드 를 저장하고

• 이동할 노드까지의 가중치와 비교해서 더 작다면 힙에 추가하는 방식으로 채택했다.

• 한가지 또 유의할 점이 있는데 현재 위치가 산봉우리에 있는지 찾을때 산봉우리가 리스트형식으로 존재하면 O(n) 이 소모가 된다

• 그래서 산봉우리리스트를 집합자료형으로 바꿔주고 찾아준다. (set은 해시테이블을 사용하기 때문에 O(1)이 걸림.)

소스코드

import heapq

def solution(n, paths, gates, summits):
    graph = [[] for _ in range(n+1)]
    INF = int(1e9)
    for a,b,c in paths:
        graph[a].append((b,c))
        graph[b].append((a,c))
    h = []
    ans = []
    distance = [INF] * (n+1)
    summits = set(summits) #집합자료형으로 변경
    def dijk():        
        for i in gates:
            heapq.heappush(h, (0,i))
            distance[i] = 0
        while h:
            dist, now = heapq.heappop(h)
            if now in summits:
                continue
            
            if distance[now] < dist:
                continue
            
            for node,cost in graph[now]:
                maxVal = max(dist, cost)
                if maxVal < distance[node]:
                    distance[node] = maxVal
                    heapq.heappush(h,(maxVal, node))
    dijk()
    for i in list(summits):
        ans.append([i,distance[i]])

    ans.sort(key=lambda x: (x[1],x[0]))
    
    return ans[0]