[프로그래머스] 등산코스 정하기 - Python

🤔 문제

---

 

프로그래머스

 

😀 풀이

---

해당 문제는 최단 경로 문제의 변형으로 최단 경로문제가 익숙하시다면 다익스트라 알고리즘을 떠올리기까지는 비교적 쉬울 것 같습니다. 다만 저처럼 아무생각 안하고 다익스트라를 적용하게되면 시간초과를 맞게됩니다..ㅠ 

 

처음 생각했던 풀이는 모든 출입구에 대하여 (출입구 -> 산봉우리 -> 출입구)의 최단경로를 구하는 방식을 사용했는데 이렇게 되면 N번의 다익스트라를 수행해야해서 시간초과가 나게되죠.

 

문제를 다시 천천히 읽어보니 2가지 포인트를 찾을 수 있었습니다.

 

첫 번째는 (출입구 -> 산봉우리), 즉 산봉우리에 오르는 경로만 생각하면 됩니다. 올라갔던 길을 다시 방문하지 않아야한다는 조건이 없고, 같은 출입구로 나와야한다는 조건이 있기 때문에 굳이 하산하는 경로는 생각하지 않아도 되는 것이죠.

 

두 번째는 모든 출입구에 대하여 다익스트라를 각각 돌릴 필요가 없다는 것입니다. 저는 이 부분을 떠올리는데 시간이 조금 걸렸는데요. 모든 출입구에서부터 시작하여 시간이 적은 길을 우선적으로 따라가다가 정상이 나오면 그게 바로 정답이 되기때문에 굳이 N번의 다익스트라 없이 한 번의 다익스트라 호출만 하면 정답을 구할 수 있습니다. 

---

💻 풀이 코드는 아래와 같습니다.

import heapq
from collections import defaultdict


def solution(n, paths, gates, summits):
    graph = defaultdict(list)

    # 그래프 만들기
    for start, end, time in paths:
        graph[start].append((end, time))
        graph[end].append((start, time))

    summits_set = set(summits)

    q = []
    visited = [False] * (n + 1)

    # 시작점들과 연결된 간선들을 큐에 넣기
    for gate in gates:
        adjs = graph[gate]
        for next_node, time in adjs:
            heapq.heappush(q, (time, next_node))

    # 답이 여러 개일 수 있어 answer_summits에 넣어두고
    # 추후 정렬하여 산봉우리가 가작 작은 것을 찾기
    answer_summits = []

    while q:
        time, node = heapq.heappop(q)

        # 산봉우리 발견
        if node in summits_set:
            answer_summits.append([node, time])
            continue

        # 이미 방문한 곳이면 넘어가기 -> 2번째 말한 포인트를 사용한 부분
        if visited[node]:
            continue
        visited[node] = True

        adjs = graph[node]
        for next_node, next_time in adjs:
            if not visited[next_node]:
                heapq.heappush(q, (max(time, next_time), next_node))
    
    # 가장 작은 산봉우리 번호를 찾기 위해 정렬
    answer_summits.sort(key=lambda x: (x[1], x[0]))
    return answer_summits[0]