[카카오] 등산코스 정하기 Python - 다익스트라 알고리즘 응용

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

프로그래머스

 

최단거리를 이용하는 다익스트라알고리즘의 응용 버전이다. 

카카오 코딩테스트 해설을 참고 했다. 

- 간선의 정보들로 인접 graph를 만든다. 그리고 문제에서 그래프 자체는 양방향 그래프인데 내가 일방향으로 처리를 해서 계속 list 에 인덱스 없다고 에러가 떴다 그래프 문제에서 양방향인지 일방향인지 항상 주의하자 ! !!!!!!
- 다익스트라 알고리즘을 출발지의 개수만큼 실행하면 시간초과가 나므로 처음에 다익스트라 알고리즘을 실행하기 이전에 출발지 노드들을 다 우선순위 큐에 push 하고 시작한다. 
- 문제에서는 최단거리를 구하는 것이 아니라, 경로에서 최소의 intensity를 구하면 된다.

intensity = [INF]*(n+1)

따라서 i번 노드까지 오는 경로에서 최소의 intensity 값을 저장할 리스트를 만든다. 

- 또한 출발지 -> summit -> 출발지로 가야 하는데, 이 경우 출발지-> summit에서 최소 intensity를 구하면, 왔던길을 똑같이 되돌아 가면 되므로 굳이 다시 summit -> 출발지까지의 경로를 구할 필요가 없다. 
즉, 출발지 -> summit 에서의 최소 intensity만 확인해주고, summit 에 해당하는 node를 발견하면 탐색 종료시킨다. 

if now in check or weight > intensity[now]:  # 산봉우리 발견
                continue  # 산봉우리이면 이동 x, 이미 더 큰 intensity면 확인할 필요 없음

또한 이미 지금 우선순위 큐에서 꺼낸 node의 intensity가 이전에 계산한 intensity보다 크다면 굳이 확인할 필요가 없으므로 
탐색 종료 조건이 된다. 

import heapq
from collections import defaultdict


def solution(n, paths, gates, summits):
    INF = 10000001
    intensity = [INF] * (n + 1)  # 출발점에서 i번 지점까지의 intensity
    graph = defaultdict(list)
    for path in paths:
        graph[path[0]].append((path[2], path[1]))  # weight, a->b 지점
        graph[path[1]].append((path[2], path[0]))
    summits.sort()
    check = set(summits)  # 탐색을 O(N)에서 O(1)로 줄인다

    # 다익스트라
    def get_intensity():
        queue = []

        # 한번에 모든 출입구를 넣는다

        for gate in gates:
            heapq.heappush(queue, (0, gate))
            intensity[gate] = 0  # 출발점 -> 출발점 자신이므로 0으로 설정
        result = [0, INF]
        while queue:
            weight, now = heapq.heappop(queue)
            if now in check or weight > intensity[now]:  # 산봉우리 발견
                continue  # 산봉우리이면 이동 x, 이미 더 큰 intensity면 확인할 필요 없음

            for i in graph[now]: # intensity, next_node
                new_intensity = max(weight, i[0])
                if new_intensity < intensity[i[1]]:
                    intensity[i[1]] = new_intensity # 최소 Intensity로 갱신해준다 (다익스트라)
                    heapq.heappush(queue, (new_intensity, i[1]))

        for summit in summits:
            if intensity[summit] < result[1]:
                result[0] = summit
                result[1] = intensity[summit]
        return result


    return get_intensity()

오오 다익스트라를 어렵게 내면 이렇게도 푸는구나 싶은 문제였다 어렵지만 그래프 문제들은 재밌다 !!