forked from tony9402/baekjoon
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathmain.py
56 lines (46 loc) · 1.14 KB
/
main.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
# Authored by : samuel95
# Co-authored by : -
# Link : http://boj.kr/56db895ff06047bb8d3cea233a924472
import sys, math
def input():
return sys.stdin.readline().rstrip()
def find(parent, a):
if parent[a] == a:
return a
parent[a] = find(parent, parent[a])
return parent[a]
def union(parent, a, b):
a = find(parent, a)
b = find(parent, b)
if a > b:
parent[a] = b
return True
elif a < b:
parent[b] = a
return True
return False
n = int(input())
# 별들의 좌표를 넣어준다.
stars = []
for i in range(n):
x,y = map(float,input().split())
stars.append([x,y])
# MST 활용을 위해 (거리,시작,끝)을 만든다.
parent = [i for i in range(n+1)]
edges = []
for i in range(n-1):
for j in range(i+1,n):
start = stars[i]
end = stars[j]
distance = math.sqrt((start[0]-end[0])**2 + (start[1]-end[1])**2)
edges.append([distance,i,j])
edges.sort()
cnt, ans = 0,0
# Union Find
for edge in edges:
if union(parent, edge[1], edge[2]):
ans += edge[0]
cnt += 1
if cnt == n - 1:
break
print(round(ans,2))