최소신장트리1 [백준 - Java] 4386번 : 별자리 만들기 문제 https://www.acmicpc.net/problem/4386 4386번: 별자리 만들기 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일 www.acmicpc.net 설명 주어진 각 별의 좌표를 이용해 모든 간선을 만들고 가중치(두 별 사이의 거리)를 저장한다. Kruskal 알고리즘을 이용해 최소 신장 트리를 구성해 최소 비용을 구한다. 크루스칼 알고리즘은 Union-Find를 이용해 구현할 수 있다. 전체 코드 import java.util.ArrayList; import java.util.Collections; import java.util.Scann.. 2021. 7. 27. 이전 1 다음 728x90 반응형