[백준] 4386번 별자리 만들기 파이썬 코드

코드

# 최소 스패닝 트리 문제
# 거리 공식으로 가중치 구해주기
# 거리 구하고 i,j점 과 함께 리스트에 추가
# 크루스칼 알고리즘 사용

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 = int(input())
parent = [i for i in range(n)]
graph = [[*map(float, input().split())] for _ in range(n)]
edge = []
for i in range(n-1):
  for j in range(i+1, n):  
    edge.append((distance(*graph[i],*graph[j]),i,j))

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