별자리 만들기

출처 : 백준 #4386

시간 제한	메모리 제한
1초	128MB

---

문제

도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다.

• 별자리를 이루는 선은 서로 다른 두 별을 일직선으로 이은 형태이다.
• 모든 별들은 별자리 위의 선을 통해 서로 직/간접적으로 이어져 있어야 한다.

별들이 2차원 평면 위에 놓여 있다. 선을 하나 이을 때마다 두 별 사이의 거리만큼의 비용이 든다고 할 때, 별자리를 만드는 최소 비용을 구하시오.

---

입력

첫째 줄에 별의 개수 n이 주어진다. (1 ≤ n ≤ 100)

둘째 줄부터 n개의 줄에 걸쳐 각 별의 x, y좌표가 실수 형태로 주어지며, 최대 소수점 둘째자리까지 주어진다. 좌표는 1000을 넘지 않는 양의 실수이다.

---

출력

첫째 줄에 정답을 출력한다. 절대/상대 오차는 10-2까지 허용한다.

---

입출력 예시

예제 입력 1

3
1.0 1.0
2.0 2.0
2.0 4.0

예제 출력 1

3.41

---

풀이

생각

• 처음에는 일반적인 dfs를 통해 풀려고 했으나 모든 노드가 연결되어 있는 점을 고려하여 최소 스패닝 트리로 풀고자 하였다.
• 모든 노드가 연결되어 있기 때문에 2중 for문을 통하여 각 노드 간의 거리를 indegree라는 최소힙에 (거리, start, end)로 넣어주었다.
• 그리고 union과 find 함수를 따로 만들어 같은 집합에 속하지 않으면, union을 통해 합쳐주고, dist를 누적으로 더해주었다.
• 마지막으로 소수점 둘째자리까지 표현하고자 round 함수를 사용하였다.
  

python code

# 백준 4386번 별자리 만들기
from sys import stdin
import math
from heapq import heappush, heappop, heapify
input = stdin.readline
INF = int(1e9)
result = 0
n = int(input())
coo = []
parents = [i for i in range(n)]
for i in range(n):
    coo.append(tuple(map(float, input().split())))
indegree = []     # 진입분지수 
results = []
for i in range(n):
    for j in range(i+1, n):
        dist = round(math.sqrt((coo[i][0] - coo[j][0])**2 + (coo[i][1] - coo[j][1])**2), 2)
        heappush(indegree, (dist, i, j))   # (거리, 온 노드의 번호)


def find(a, parents):
    if parents[a] != a:
        parents[a] = find(parents[a], parents)
    return parents[a]

def union(a, b, parents):    
    a = find(a, parents)
    b = find(b, parents)
    if a < b:
        parents[b] = a
    else:
        parents[a] = b

while indegree:
    dist, a, b = heappop(indegree)
    if find(a, parents) != find(b, parents):
        union(a, b, parents)
        result += dist

print(round(result, 2))