모든 마을을 잇는 최소 비용
레벨 M2 · 코딩 · JavaScript · 목표 시간 18분 · 게시일 2026-10-24
0번부터 n-1번까지의 마을과 지을 수 있는 양방향 도로 후보 roads([a, b, 비용])가 주어진다. 도로를 골라 지어 모든 마을이 서로 오갈 수 있게 할 때 드는 비용 합의 최솟값을 구하시오. 어떻게 해도 모두 이을 수 없으면 -1이다. 마을이 하나이면 0이다.
n은 최대 50,000, 도로 후보는 최대 100,000개, 비용은 1 이상 1,000,000 이하이다. 같은 두 마을 사이에 후보가 여럿이거나 a = b인 후보가 있을 수도 있다.
예제
solve(4, [[0,1,1],[1,2,2],[2,3,1],[0,3,4],[0,2,3]]) solve(3, [[0,1,5]]) solve(1, [])