[프로그래머스] 등산코스 - python

https://school.programmers.co.kr/learn/courses/30/lessons/118669

프로그래머스

다익스트라를 활용하여 풀 수 있는 문제입니다. 이 문제의 경우에는 출발 지점 -> 산봉우리 -> 출발지점으로 되돌아와야하지만 경로의 길이를 구하는 것이 아니라 최소의 intensity를 구하는 것이기 때문에 출발지점 -> 산봉우리에 대한 다익스트라로 봐도 무방합니다(산봉우리를 향해 올라갔던 경로 그대로 되돌아오면 되기 때문에).

 

현재의 지점에서 다음 지점으로 넘어가기 위해서는 두가지 중 하나를 만족해야합니다. 다음 지점을 처음 방문하는 경우이거나 더 짧은 intensity로 갱신하는 경우에만 탐색을 진행해주면 됩니다.

 

그리고 다음 지점이 출발지점이 아닌 경우에만 탐색을 지정해주어야합니다. 어차피 모든 경로가 출발점에서 시작하기 때문에 굳이 방문할 필요가 없기 때문입니다.

 

또, 한가지는 현재가 산봉우리인 경우에는 어차피 도착점에 도달했기 때문에 추가적으로 탐색하지 않습니다. 이미 산봉우리를 방문했는데 또 방문하면 안되기 때문입니다(입출력 예 #3의 경우).

 

마지막으로 조심해야하는 점은 산봉우리를 만난 경우에는 더이상 탐색하지 않으므로 방문되지 않은 산봉우리가 있을 수 있습니다. ex) 출발 - 쉼터 - 산봉우리 - 산봉우리 와 같은 그래프에 대해서는 최초에 만나는 산봉우리까지만 intensity가 측정되게 됩니다.

 

import sys, heapq
from collections import defaultdict

graph = defaultdict(list)
summit_set = set()
gate_set = set()
INF = sys.maxsize

def dijkstra(n, gates):
    dist = [-1] * (n + 1)
    pq = []
    for g in gates:
        dist[g] = 0
        heapq.heappush(pq, (0, g))

    while pq:
        intensity, cur = heapq.heappop(pq)
        
        # 이미 intensity가 갱신되었거나 현재 산봉우리인 경우 탐색하지 않음
        if intensity != dist[cur] or cur in summit_set:
            continue

        for target, target_intensity in graph[cur]:
            if target in gate_set:
                continue

            next_intensity = max(target_intensity, intensity)

            # 최초 탐색이거나 더 짧은 intensity로 방문할 수 있는 경우 탐색
            if dist[target] < 0 or dist[target] > next_intensity:
                dist[target] = next_intensity
                heapq.heappush(pq, (next_intensity, target))

    return dist

def solution(n, paths, gates, summits):
    answer = [-1, INF]

    for i, j, w in paths:
        graph[i].append((j, w))
        graph[j].append((i, w))

    summits.sort()
    gates.sort()

    for s in summits:
        summit_set.add(s)

    for g in gates:
        gate_set.add(g)

    dist = dijkstra(n, gates)

    for s in summits:
        # intensity가 없는 산봉우리가 있을 수 있음
        if dist[s] != -1 and dist[s] < answer[1]:
            answer[0] = s
            answer[1] = dist[s]

    return answer