[골드4] 4386번 : 별자리 만들기

🛠 문제

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

👩🏻‍💻 해결 방법

모든 별들 간의 거리를 구해준 뒤 정렬하여 최소비용을 구할 수 있는 문제다
별의 위치를 좌표로 입력받았기 때문에 별자리 간의 거리를 math를 사용해 구해주었다

소스 코드

import math

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

def union_parent(parent, a, b):
  a = find_parent(parent, a)
  b = find_parent(parent, b)

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

n = int(input())
stars = []

for _ in range(n):
  x, y = map(float, input().split())
  stars.append((x, y))

parent = [i for i in range(n)]
edges = []
result = 0

for i in range(n-1):
  for j in range(i+1, n):
    edges.append((math.sqrt((stars[i][0]-stars[j][0])**2 + (stars[i][1]-stars[j][1])**2), i, j))

edges.sort()

for edge in edges:
  cost, x, y = edge

  if find_parent(parent, x) != find_parent(parent, y):
    union_parent(parent, x, y)
    result += cost

print(round(result, 2))