2022 KAKAO TECH INTERNSHIP 풀이

Level 1 - 성격 유형 검사하기 풀이
Level 2 - 두 큐 합 같게 만들기 풀이
Level 3 - 코딩 테스트 공부 풀이
Level 3 - 등산코스 정하기 풀이
Level 4 - 행렬과 연산 풀이

프로그래머스 - 등산코스 정하기 링크
(2022.10.26 기준 Level 3)

문제

하나의 출입구만을 사용하여 하나의 산봉우리만을 방문하여 등산할 때 쉼터 또는 산봉우리에서 휴식을 취할 수 있고 휴식 없이 이동해야 하는 시간 중 가장 긴 시간을 intensity 라고 한다. 그렇다면 intensity가 최소가 되도록 등산코스를 정한다면 그 등산코스의 산봉우리 번호와 intensity 반환

알고리즘

특정한 조건을 걸어야 하는 max 연산을 통한 거리를 계산하는 다익스트라

풀이

intensity는 결국 등산코스의 간선 중 제일 가중치가 높은 간선의 가중치를 뜻한다.
등산코스는 왕복이지만 어차피 돌아올 때는 똑같은 루트로 돌아오면 되므로 편도라고 가정해도 무방하다.

다익스트라는 현재 위치의 최단 거리와 다음 위치의 최단 거리 + 간선 가중치를 비교하여 최단 거리를 계산하는 것이다.
하지만 이 문제는 제일 가중치가 높은 간선의 가중치가 최소가 되도록 해야 한다. 결국은 각 위치에 대해 도달하기 위한 최소 가중치를 구해야 하는 것이다.
이는 distance[현재 위치] > max(distance[다음 위치], 현재-다음 가중치) 연산을 통해 다익스트라를 돌리면 된다.

시작 위치는 gates의 원소들이다. 그러므로 gates의 모든 번호를 시작 위치로 정해주고 distance[gate] = 0을 해주자.
이렇게 하면 다른 출입구로 나가는 일이 생기지 않는다.

그리고 제일 중요한 점이 있다.
두 개 이상의 산봉우리를 방문하면 안된다. 그러므로 산봉우리를 방문하는 즉시 continue 하게 만들어야 한다.
그렇지 않으면 세번째 예제에서 오류를 범하게 된다.

코드

import heapq
from math import inf

def solution(n, paths, gates, summits):
    # 간선 정리 (양방향)
    graph = [[] for _ in range(n + 1)]
    for i, j, w in paths:
        graph[i].append([j, w])
        graph[j].append([i, w])

    # 산봉우리 판별
    is_summit = [False] * (n + 1)
    for summit in summits:
        is_summit[summit] = True

    # gates 모두 시작 위치
    distance = [inf] * (n + 1)
    queue = []
    for gate in gates:
        distance[gate] = 0
        heapq.heappush(queue, [0, gate])

    # 다익스트라
    while queue:
        d, i = heapq.heappop(queue)
        # 산봉우리면 바로 continue
        # 이렇게 해야 두 개 이상의 산봉우리를 방문하지 않는다.
        if distance[i] < d or is_summit[i]:
            continue
        for j, dd in graph[i]:
            dd = max(distance[i], dd)
            if distance[j] > dd:
                distance[j] = dd
                heapq.heappush(queue, [dd, j])

    # 결과
    # 거리가 같으면 산봉우리의 번호가 작은 것을 출력해야 하므로
    # 산봉우리를 정렬하여 살펴보자.
    result = [-1, inf]
    for summit in sorted(summits):
        if distance[summit] < result[1]:
            result[0] = summit
            result[1] = distance[summit]
    return result