# BOJ - 1774 - 우주신과의 교감

Updated:

``````import sys
import math
import heapq

def getDistance(x1, x2):
return (
math.sqrt(
math.pow(x1[0] - x2[0], 2) + math.pow(x1[1] - x2[1], 2)
)
)

def find(parent, x):
if (parent[x] == x): return x
parent[x] = find(parent, parent[x])
return parent[x]

def unionx(parent, x, y):
rootX = find(parent, x)
rootY = find(parent, y)
if not rootX == rootY: parent[rootY] = rootX

def solution():
graph = []
count = 0
parent = [i for i in range(N+1)]
point = [[0, 0]]

for _ in range(N):
point.append([X, Y])

for _ in range(M):
if find(parent, X) != find(parent, Y):
unionx(parent, X, Y)
count += 1

for i in range(1, N):
for j in range(i+1, N+1):
distance = getDistance(point[i], point[j])
heapq.heappush(graph, [distance, i, j])

ans = 0
while graph:
weight, start, end = heapq.heappop(graph)
if find(parent, start) != find(parent, end):
unionx(parent, start, end)
ans += weight
count += 1
if count == N:
break

print("%0.2f"%ans)

solution()
``````

https://www.acmicpc.net/problem/1774

Categories:

Updated: