문제 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일직선으로 이은 형태이다. 모든 별들은 별자리 위의 선을 통해 서로 직/간접적으로 이어져 있어야 한다. 별들이 2차원 평면 위에 놓여 있다. 선을 하나 이을 때마다 두 별 사이의 거리만큼의 비용이 든다고 할 때, 별자리를 만드는 최소 비용을 구하시오. 풀이 이 문제는 최소 스패닝트리를 이용해 푸는 문제다. 필자는 크루스칼 알고리즘을 이용해서 문제를 풀었다. 알고리즘 순서는 다음과 같다. 모든 점과 점의 사이 거리를 구해 PriorityQueue에 넣어준다. 사이 거리가 작은 순부터 차례대로 사이클을 형성하지 않는 거..