문제 요약
출입구에서 출발해 산봉우리 하나를 방문한 뒤, 출발했던 출입구로 돌아오는 등산코스를 정해야 한다.
등산코스의 intensity는 코스에 포함된 등산로 중 가장 긴 이동 시간이다. 따라서 다음 조건을 만족하는 결과를 구해야 한다.
- intensity가 가장 작은 산봉우리를 선택한다.
- 최소 intensity가 같은 산봉우리가 여러 개라면 번호가 가장 작은 산봉우리를 선택한다.
- 코스 중간에 다른 출입구나 다른 산봉우리를 방문하면 안 된다.
핵심 아이디어
일반적인 최단 경로 문제는 경로에 포함된 간선 가중치의 합을 최소화한다. 하지만 이 문제는 간선 가중치의 합이 아니라 경로에서 가장 큰 간선 가중치를 최소화해야 한다.
현재 지점까지의 최소 intensity가 current_intensity이고, 다음 등산로의 이동 시간이 weight라면 다음 지점까지의 intensity는 다음과 같다.
next_intensity = max(current_intensity, weight)이 값을 기준으로 다익스트라 알고리즘을 수행하면 각 지점까지 도달하는 최소 intensity를 구할 수 있다.
또한 출입구가 여러 개이므로 모든 출입구를 우선순위 큐에 동시에 넣는 다중 시작점 다익스트라를 사용한다.
왕복 경로를 따로 계산하지 않아도 되는 이유
등산로는 양방향이다. 출입구에서 산봉우리까지 이동한 경로를 그대로 거꾸로 돌아오면 원래 출입구로 복귀할 수 있다.
같은 등산로를 왕복하더라도 intensity는 이동 시간의 합이 아니라 가장 긴 등산로의 이동 시간이므로 변하지 않는다.
따라서 출입구에서 산봉우리까지의 최소 intensity만 구하면 왕복 코스의 최소 intensity도 함께 구한 셈이 된다.
풀이 과정
1. 그래프 생성
각 등산로는 양방향이므로 인접 리스트에 양쪽 방향을 모두 저장한다.
graph[a].append((b, weight))
graph[b].append((a, weight))2. 모든 출입구를 시작점으로 설정
각 출입구까지의 intensity를 0으로 초기화하고 우선순위 큐에 넣는다.
for gate in gates:
intensity[gate] = 0
heappush(heap, (0, gate))이렇게 하면 각 지점에 대해 모든 출입구 중 가장 유리한 출입구에서 출발한 최소 intensity가 계산된다.
3. 산봉우리에서는 탐색 중단
산봉우리는 코스에서 한 번만 방문해야 하며 최종 목적지 역할을 한다. 따라서 산봉우리에 도착한 뒤에는 인접한 지점으로 탐색을 이어가지 않는다.
if node in summit_set:
continue이 처리로 어떤 산봉우리를 거쳐 다른 산봉우리로 이동하는 잘못된 경로를 차단할 수 있다.
4. 최소 intensity 갱신
현재 경로의 intensity와 새로 이동할 등산로의 이동 시간 중 큰 값을 다음 지점까지의 intensity로 사용한다.
next_intensity = max(current_intensity, weight)기존에 기록한 값보다 작을 때만 갱신하고 우선순위 큐에 추가한다.
5. 산봉우리 선택
산봉우리 번호를 오름차순으로 확인한다. 더 작은 intensity가 발견될 때만 정답을 갱신하면, intensity가 같은 경우 번호가 작은 산봉우리가 자연스럽게 유지된다.
Python 코드
from heapq import heappop, heappush
def solution(n, paths, gates, summits):
graph = [[] for _ in range(n + 1)]
for a, b, weight in paths:
graph[a].append((b, weight))
graph[b].append((a, weight))
summit_set = set(summits)
infinity = float("inf")
# intensity[node] = 출입구 중 한 곳에서 node까지의 최소 intensity
intensity = [infinity] * (n + 1)
heap = []
# 모든 출입구를 동시에 시작점으로 사용한다.
for gate in gates:
intensity[gate] = 0
heappush(heap, (0, gate))
while heap:
current_intensity, node = heappop(heap)
# 이미 더 좋은 경로가 처리된 상태라면 건너뛴다.
if current_intensity > intensity[node]:
continue
# 산봉우리는 목적지이므로 다른 지점으로 이동하지 않는다.
if node in summit_set:
continue
for next_node, weight in graph[node]:
next_intensity = max(current_intensity, weight)
if next_intensity < intensity[next_node]:
intensity[next_node] = next_intensity
heappush(heap, (next_intensity, next_node))
answer_summit = -1
answer_intensity = infinity
for summit in sorted(summits):
if intensity[summit] < answer_intensity:
answer_summit = summit
answer_intensity = intensity[summit]
return [answer_summit, answer_intensity]출입구를 경로 중간에 방문하지 않는 이유
모든 출입구의 intensity는 처음부터 0이다. 다른 지점에서 출입구로 이동해 계산한 intensity는 반드시 0 이상이므로 해당 출입구의 값을 더 작게 갱신할 수 없다.
따라서 다른 출입구로 들어온 경로가 그 출입구를 지나 다시 확장되는 일은 없다. 별도의 출입구 방문 차단 조건 없이도 출입구는 시작점으로만 사용된다.
정확성
다익스트라 탐색에서 우선순위 큐에는 현재까지 알려진 intensity가 작은 상태부터 들어간다.
한 지점까지 intensity가 x인 경로에 가중치 w인 등산로를 추가했을 때 새 intensity는 max(x, w)이다. 이 값은 기존 intensity보다 작아질 수 없으므로 다익스트라의 탐욕적인 처리 순서를 적용할 수 있다.
따라서 탐색이 끝난 뒤 intensity[v]에는 모든 출입구에서 v까지 갈 수 있는 경로 중 가장 작은 intensity가 저장된다. 산봉우리에서는 탐색을 중단하므로 다른 산봉우리를 경유한 경로도 포함되지 않는다.
마지막으로 산봉우리를 번호순으로 확인하여 최소 intensity를 선택하므로 문제의 우선순위 조건도 만족한다.
시간 복잡도
지점 수를 V, 등산로 수를 E라고 하면 다익스트라 탐색의 시간 복잡도는 다음과 같다.
O((V + E) log V)산봉우리 정렬에는 O(S log S)가 필요하며, S는 산봉우리 수이다.
공간 복잡도
인접 리스트, intensity 배열, 우선순위 큐를 사용하므로 공간 복잡도는 다음과 같다.
O(V + E)정리
이 문제는 이동 시간의 합이 아니라 경로에서 가장 큰 이동 시간을 최소화하는 최소 최대 경로 문제다.
모든 출입구를 시작점으로 하는 다중 시작점 다익스트라를 사용하고, 경로 확장 비용을 max(현재 intensity, 등산로 시간)으로 계산하면 효율적으로 해결할 수 있다. 산봉우리에서 탐색을 중단하는 것이 코스 조건을 지키는 핵심이다.
