[백준] 1774번 우주신과의 교감 파이썬 코드

코드

def distance(x1, y1, x2, y2):
  dist = ((x2-x1)**2 + (y2-y1)**2)**0.5
  return dist

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

def union(a,b,lst):
  a = find(a,lst)
  b = find(b,lst)

  if a < b:
    lst[b] = a
  else: lst[a] = b

import sys
sys.setrecursionlimit(10**5)
input = sys.stdin.readline

n,m = map(int, input().split())
parent = [i for i in range(n+1)]
graph = [0]

for _ in range(n):
  x,y = map(int, input().split())
  graph.append((x,y))
for _ in range(m):
  x,y = map(int, input().split())
  union(x,y,parent)
  
edge = []

for i in range(1, n):
  for j in range(i+1,n+1):
    edge.append((distance(*graph[i],*graph[j]),i,j)) # 좌표 간의 거리 기록
edge.sort()

res = 0
for edges in edge:
  if find(edges[1], parent) != find(edges[2], parent):
    res += edges[0]
    union(edges[1], edges[2], parent)
print(f'{res:.2f}')