문제 https://www.acmicpc.net/problem/4386 4386번: 별자리 만들기 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일 www.acmicpc.net 문제 풀이 해당 문제는 MST(Minimum Spanning Tree) 알고리즘을 사용하는 문제이다. 왜냐하면 N개의 정점(별)을 이어서 그래프(별)를 만드는데 최소의 비용을 구하라는 문제이기 때문이다. 원래 MST의 문제라면 정점간의 간선에 가중치를 입력으로 제공하지만, 해당 문제는 각 좌표를 제공해서, 정점 간의 거리까지 구하는 문제이다. 가중치를 제공해주지 않았기 때문에 MST를 제대로 ..
