별자리 만들기
-
[백준]4386: 별자리 만들기 - JAVA문제풀이/백준 2021. 4. 26. 19:04
[백준]4386: 별자리 만들기 www.acmicpc.net/problem/4386 4386번: 별자리 만들기 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일 www.acmicpc.net 풀이 별들의 좌표를 간선으로 이었을때 최소인 비용을 찾는 문제로 MST알고리즘을 사용하여 풀면 된다. 별을 입력받을때 해당 별의 번호와 좌표를 저장해 주었다. 이 문제에서는 별들이 연결된 간선의 정보가 없으므로 모든 별들 사이의 거리를 직접 구하여 간선list에 저장해 주었다. 그다음 MST알고리즘인 prim, kruskal알고리즘을 사용하여 각각의 MST를 구해주면 된다. 코드 ..