최대 위험도를 최소화하는 탈출 경로

자바스크립트 코딩테스트 문제로 minimax-path 주제를 연습해보세요. 난이도는 hard이며, 브라우저에서 바로 JavaScript로 풀이를 실행할 수 있습니다.

today hard minimax-path 함수명: minimumEscapeRiskPath 제한 시간: 400ms

그래프에서 출발점부터 도착점까지 이동할 때, 지나간 간선들 중 가장 큰 위험도가 가능한 한 작아지도록 경로를 골라야 합니다.

문제 설명

정점 개수가 n개인 무방향 가중치 그래프가 주어집니다. 각 간선은 [u, v, risk] 형태이며, u와 v를 양방향으로 연결하고 그 간선을 지날 때의 위험도가 risk입니다.

경로의 총 비용은 간선 위험도의 합이 아니라, 그 경로에서 지나간 간선들 중 가장 큰 위험도 1개로 정의합니다.

start에서 end까지 가는 모든 경로 중에서 이 값이 가장 작은 값을 반환하는 minimumEscapeRiskPath 함수를 작성하세요. 도달할 수 없으면 -1을 반환합니다.

예를 들어 어떤 경로의 간선 위험도가 [4, 1, 6, 2]라면 이 경로의 비용은 13이 아니라 6입니다.

제한사항

2 <= n <= 200000
0 <= edges.length <= 300000
edges[i] = [u, v, risk]
1 <= u, v <= n
u !== v
1 <= risk <= 10^9
그래프에는 중복 간선이 있을 수 있습니다.
1 <= start, end <= n
start === end이면 정답은 0입니다.

예시

입력: n = 5, edges = [[1,2,4],[2,5,3],[1,3,8],[3,4,2],[4,5,2],[2,3,5]], start = 1, end = 5 → 출력: 4
입력: n = 4, edges = [[1,2,7],[2,4,7],[1,3,2],[3,4,9]], start = 1, end = 4 → 출력: 7
입력: n = 3, edges = [[1,2,5]], start = 1, end = 3 → 출력: -1
입력: n = 6, edges = [[1,2,10],[1,3,6],[3,4,6],[4,6,6],[2,6,3],[3,5,2],[5,6,8]], start = 1, end = 6 → 출력: 6

힌트

어떤 경로가 더 좋은지는 간선 합이 아니라 현재까지 본 최대 위험도로 비교해야 합니다.
정점 next로 갈 때 새 비용은 currentCost + risk가 아니라 Math.max(currentCost, risk)입니다.
“지금까지 찾은 next의 최소 병목값”보다 더 작은 값으로 갱신될 때만 다시 볼 가치가 있습니다.

해설

이 문제는 일반적인 최단 경로와 비교 기준이 다릅니다.

보통 다익스트라는 간선 비용의 합을 최소화하지만, 여기서는 경로 비용이 지금까지 지나온 간선 중 최댓값입니다. 따라서 어떤 정점까지 가는 현재 비용을 dist[x] = x까지 가는 경로들 중 최소 가능한 최대 위험도라고 정의해야 합니다.

정점 cur에서 간선 위험도 risk를 통해 next로 이동하면, 새 경로의 비용은

Math.max(dist[cur], risk)

입니다. 왜냐하면 새 경로에서 가장 위험한 간선은

원래 cur까지 오면서 이미 본 최대 위험도이거나
방금 건넌 간선의 위험도 둘 중 더 큰 값이기 때문입니다.

이제 우선순위 큐에 (현재 병목값, 정점)을 넣고, 병목값이 더 작은 상태부터 꺼내며 완화(relaxation)하면 됩니다.

풀이 흐름은 다음과 같습니다.

인접 리스트를 만듭니다.
dist 배열을 Infinity로 채우고 dist[start] = 0으로 둡니다.
우선순위 큐에서 현재 병목값이 가장 작은 정점을 꺼냅니다.
인접한 간선마다 nextCost = Math.max(currentCost, risk)를 계산합니다.
nextCost < dist[next]이면 갱신하고 큐에 넣습니다.
end를 처음 꺼낸 순간 그 값이 정답입니다.

이 방식이 맞는 이유는, 병목값 기준으로도 “더 작은 값이 항상 더 유리하다”는 단조성이 있기 때문입니다. 이미 어떤 정점에 더 작은 최대 위험도로 도달했다면, 그보다 큰 최대 위험도로 같은 정점에 다시 도달한 상태는 이후 경로를 확장해도 절대 더 좋아질 수 없습니다.

시간 복잡도는 우선순위 큐를 사용할 때 O((n + m) log n) 수준이고, 큰 그래프도 충분히 처리할 수 있습니다.

코드 작성

starter code를 바탕으로 함수를 완성한 뒤 예제 테스트를 실행해보세요.

JavaScript 에디터 로딩 중...

커스텀 테스트

함수 인자를 JSON 배열 형태로 입력하세요. 예: [3, 5], [[1, 2, 3]]

아직 실행하지 않았습니다.

실행 결과