2022 KAKAO TECH INTERNSHIP - 등산코스 정하기 (파이썬) 문제 및 풀이

문제

programmers.co.kr/learn/courses/30/lessons/118669
XX산의 지점 수 n, 각 등산로의 정보를 담은 2차원 정수 배열 paths, 출입구들의 번호가 담긴 정수 배열 gates, 산봉우리들의 번호가 담긴 정수 배열 summits가 매개변수로 주어집니다. 이때, intensity가 최소가 되는 등산코스에 포함된 산봉우리 번호와 intensity의 최솟값을 차례대로 정수 배열에 담아 return 하도록 solution 함수를 완성해주세요. intensity가 최소가 되는 등산코스가 여러 개라면 그중 산봉우리의 번호가 가장 낮은 등산코스를 선택합니다.

풀이

그래프에서의 최단 intensity로 갈 수 있는 등산 코스를 짜는 문제입니다. 무방향 가중치 그래프이고 intensity가 최소가 되는 경로를 만들어야 되므로 다익스트라 알고리즘을 이용합니다. gate에서 summit까지의 최소 intensity와 summit에서 gate까지 최소 intensity가 같다는 점을 이용하여 gate에서 summit까지 한 번만 다익스트라 알고리즘을 적용합니다.

코드

import heapq
INF = int(1e9)

def solution(n, paths, gates, summits):
    summits.sort()
    summits_set = set(summits)
    graph = [[] for _ in range(n + 1)]
    for i, j, w in paths:
        graph[i].append([j, w])
        graph[j].append([i, w])

    pq = []
    distance = [INF] * (n + 1)

    for gate in gates:
        heapq.heappush(pq, (0, gate))
        distance[gate] = 0

    while pq:
        intensity, now = heapq.heappop(pq)

        if now in summits_set or intensity > distance[now]:
            continue

        for next, cost in graph[now]:
            new_intensity = max(intensity, cost)
            if new_intensity < distance[next]:
                distance[next] = new_intensity
                heapq.heappush(pq, (new_intensity, next))

    result = [0, INF]

    for summit in summits_set:
        if distance[summit] < result[1]:
            result[0] = summit
            result[1] = distance[summit]
    return result

회고

오랜만에 적용하는 다익스트라 알고리즘으로 예전에 해결했던 백준 풀이를 참고했습니다. 알고리즘 구현이 어렵지 않도록 더욱 훈련해야겠습니다.