등산코스 정하기 (Python)

접근 방법

1. (다익스트라) 한 노드에서 특정 노드까지 경로 중 최적의 조건을 만족하는 값을 구하는 문제이기 때문에 다익스트라를 적용할 수 있다
2. (최적화) 경로의 조건 중 중복 조건 혹은 최소 조건은 없기 때문에, 모든 게이트 노드에서 각 노드에 도달하기 까지의 최대 쉬는 시간은 공유된 것처럼 봐도 무방하다. 그렇기 때문에 모든 게이트 노드에서 동시에 시작하면 연산 시간을 아낄 수 있다.
3. (최적의 조건) 모든 노드의 최대 휴식 시간을 기억하고 있는 weights 배열을 두고, 모든 게이트 노드를 우선순위큐에 넣는다. 큐에서 뺄 때마다 a) 현재까지 가장 긴 휴식시간과 b) 종착지 노드가 나올 텐데, 이 때 a의 값이 weights 배열의 종착지 노드 위치의 값보다 크면 이미 최적 조건 달성을 못하기 때문에 continue한다. 또는 종착지 노드가 꼭대기 노드인 경우, 어차피 뒤돌아 가면 되기 때문에 continue한다. 그 후, 해당 종착지 노드에서 갈 수 있는 모든 노드들까지의 휴식 시간과 현재까지의 제일 큰 휴식 시간 값을 비교해서, 전자가 더 작다면 weights 배열을 해당 값을 초기화하고 우선순위 큐에 넣어준다.

코드

from heapq import heappop, heappush, heapify

def solution(n, paths, gates, summits):
    graph = [[] for _ in range(n + 1)]

    for a, b, w in paths:
        graph[a].append((b, w))
        graph[b].append((a, w))

    is_summit = [False] * (n + 1)
    for summit in summits:
        is_summit[summit] = True

    q = []
    weights = [1e9 for _ in range(n + 1)]
    for gate in gates:
        weights[gate] = 0
        heappush(q, [0, gate])

    while q:
        d, i = heappop(q)
        if weights[i] < d or is_summit[i]:
            continue
        for j, dd in graph[i]:
            dd = max(weights[i], dd)
            if weights[j] > dd:
                weights[j] = dd
                heappush(q, [dd, j])

    answer = [-1, 1e9]
    for summit in sorted(summits):
        if weights[summit] < answer[1]:
            answer[0] = summit
            answer[1] = weights[summit]
    return answer

복기