JS-L4-023 / 고급 알고리즘
최소 신장 트리
고급문제
0부터 n-1까지 노드와 무방향 가중 간선 [a,b,w]를 받습니다. 최소 신장 트리 비용 또는 연결 불가능하면 -1을 반환하세요. n은 1 이상입니다.
solve(...args) 함수에서 값을 반환하세요. console 출력은 정답 판정에 사용하지 않습니다.
입출력 예시
예제 1
입력: [3,[[0,1,2],[1,2,5],[0,2,3]]] 반환: 5
예제 2
입력: [2,[]] 반환: -1
힌트
작은 가중치 간선부터 서로소 집합으로 선택하세요.
해설·정답 보기
Kruskal 알고리즘입니다. 입력 간선을 복사해 정렬하고 선택 개수로 연결 여부를 확인합니다.
function solve(n,edges) { const p=Array.from({length:n},(_,i)=>i); const find=x=>p[x]===x?x:(p[x]=find(p[x])); let sum=0,count=0; for(const [a,b,w] of [...edges].sort((x,y)=>x[2]-y[2])){const x=find(a),y=find(b);if(x!==y){p[x]=y;sum+=w;count++;}} return count===n-1?sum:-1; }solution.js결과 비교
코드는 이 브라우저에 자동 저장돼요.
풀이 결과
코드를 작성하고 채점하기를 눌러보세요.
학습용으로 제공된 조건을 확인해요. 알고리즘 사용 방식·설계 의도는 해설과 함께 비교해보세요.