[programmers] Lv3 등산코스 정하기 - Python

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

프로그래머스

 

 

 

<문제 풀이>

- 게이트에서 산봉우리까지 가는 길만 판단하면 된다. 어차피 같은 길로 내려오면 되니까. 

- heap을 이용하면 보다 시간복잡도도 해결되고 최소값을 먼저 꺼내 확인할 수 있다.

- summits을 set 자료형 변환하여 봉우리인지 확인할 때 시간을 줄일 수 있다.

 

 

 

<Code>

from collections import defaultdict
import heapq


def solution(n, paths, gates, summits):
    answer = []
    summits = set(summits)
    mt = defaultdict(list)    # 길 정보
    for a, b, c in paths:    # 양방향으로 길 정보 저장
        mt[a].append((b, c))
        mt[b].append((a, c))

    q = []
    visited = [10000001] * (n+1)    # 방문지 체크, 주어진 조건 최대값을 각 위치에 저장
    for gate in gates:
        heapq.heappush(q, [0, gate])    # [gate, intensity]
        visited[gate] = 0    # 출입구 방문 체크

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

        # 산봉우리에 도착하거나 intensity가 더 큰 지점은 더 이상 이동하지 않는다.
        if (now in summits) or (intensity > visited[now]):
            continue

        for nxt, time in mt[now]:    # 현 위치에서 갈 수 있는 곳 찾기
            temp = max(intensity, time)    # 다음 위치와 현 위치 중 시간이 큰 것을 temp에 저장
            # temp보다 작은 경우는 지나온 길이기 때문에 체크하지 않는다.
            if temp < visited[nxt]:
                visited[nxt] = temp
                heapq.heappush(q, [temp, nxt])

    for summit in summits:
        answer.append([summit, visited[summit]])

    answer.sort(key=lambda x: (x[1], x[0]))    # 1순위 intensity, 2순위로 산봉우리 번호로 오름차순 정렬

    return answer[0]

※ 잘못된 점, 개선점 등이 있다면 언제든 댓글로 알려주시면 감사하겠습니다.