프로그래머스 등급3 - 등산코스 정하기

배달 문제 바로 가기

풀이 날짜: 2026-05-19

baekjoon 알고리즘 문제 풀이

풀이 코드


import heapq

def solution(n, paths, gates, summits):
    answer = []
    
    INF = int(1e9)
    
    graph = [[] for i in range(n+1)]
    for i in paths:
        a = i[0]
        b = i[1]
        c = i[2]
        graph[a].append((b,c))
        graph[b].append((a,c))
        
    gate_set = set(gates)
    summit_set = set(summits)
    
    def dijkstra(start):
        distance = [INF] * (n+1)
        q = []
        
        for gate in gates:
            distance[gate] = 0
            heapq.heappush(q,(0,gate))
        
        while q:
            dist, now = heapq.heappop(q)
            
            if distance[now] < dist:
                continue
                
            if now in summit_set:
                continue
            
            for i in graph[now]:
                next_node = i[0]
                weight = i[1]
                
                if next_node in gate_set:
                    continue
                
                cost = max(dist, weight)
                if cost < distance[next_node]:
                    distance[next_node] = cost
                    heapq.heappush(q,(cost,next_node))
        
        for summit in summit_set:
            answer.append((summit,distance[summit]))
        
    dijkstra(gates[0])
        
    answer.sort(key=lambda x: (x[1],x[0]))
        
    return answer[0]

접근 방법 (아이디어)

이 문제는 일반적인 최단 거리 문제처럼 “거리의 합”을 최소화하는 문제가 아니라, 경로를 이동하면서 만나는 간선 비용들 중 가장 큰 값을 최소화하는 문제였다. 즉, 특정 경로의 총 이동 비용이 아니라 “가장 힘든 구간의 난이도(Intensity)”를 최소화해야 한다는 점이 핵심이었다.

그래프 구성

각 노드에는 (다음 노드, 가중치) 형태로 연결 정보를 저장했다. 이후 다익스트라 탐색 과정에서 현재 노드와 연결된 다음 노드들을 순회하며 intensity를 계산할 수 있도록 했다.

graph[a].append((b, c))
graph[b].append((a, c))

gate와 summit를 set으로 저장한 이유

출입구(gates)와 산봉우리(summits)는 탐색 과정에서 매우 자주 포함 여부를 검사하게 된다. 리스트(list)는 포함 여부를 검사할 때 매번 처음부터 끝까지 탐색해야 하지만, set은 해시 기반 자료구조이기 때문에 훨씬 빠르게 탐색할 수 있다. 따라서 시간 복잡도를 줄이기 위해 set으로 변환하여 사용했다.

다익스트라 함수 유지

기존에 사용하던 def dijkstra(start): 구조를 최대한 유지하면서 문제 조건에 맞게 수정했다.

처음에는 gate마다 다익스트라를 각각 실행했지만

for start in gates: dijkstra(start)

이 방식은 gate의 개수만큼 전체 그래프를 반복 탐색하게 되어 시간 초과가 발생했다.

모든 gate를 동시에 시작점으로 처리

시간 초과를 해결하기 위해 “멀티 소스 다익스트라(Multi Source Dijkstra)” 방식으로 변경했다.

즉, 하나의 시작점만 큐에 넣는 것이 아니라 모든 출입구를 시작점으로 동시에 우선순위 큐에 넣었다. 이렇게 하면 여러 gate 중 intensity가 가장 작은 경로가 자동으로 먼저 탐색되므로, 별도로 gate마다 탐색할 필요가 없어진다.

일반 다익스트라와의 차이점

일반적인 다익스트라에서는 누적 거리 합을 계산한다.

cost = dist + weight 하지만 이 문제에서는 경로의 총합이 아니라, 지금까지 지나온 간선 중 가장 큰 값을 intensity로 사용해야 한다.
cost = max(dist, weight)

즉 현재까지 현재까지 intensity가 dist, 다음 간선 비용이 weight라면 새로운 intensity는 둘 중 더 큰 값이 된다.

summit에 도착하면 탐색 종료

문제 조건상 산봉우리에 도착하면 더 이상 이동하면 안 된다. 따라서

if now in summit_set: continue 를 통해서 산봉우리 이후 경로는 탐색하지 않도록 했다. —
gate 재방문 방지

출입구는 시작점 역할만 해야 하므로 탐색 도중 다른 gate로 이동하는 경우는 제외했다.

정답 선택

탐색이 끝난 뒤 각 산봉우리의 intensity를 answer 리스트에 저장했다. 이후에 answer.sort(key=lambda x: (x[1],x[0]))를 통해서

ntensity가 가장 작은 산봉우리
intensity가 같다면 번호가 가장 작은 산봉우리 순으로 정렬했다. 마지막으로 첫 번째 값을 반환하여 최종 정답을 구했다.

Vienna sausage