[백준 4386] 별자리 만들기: 크루스칼 파이썬, python

1.  문제

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

4386번: 별자리 만들기

2. 풀이

어려웠던 부분은 별이 2차원인데 1차원의 parent에 어떻게 표시하나였다.

1번 별(예: 1.0 1.0)을 0 번, 2번 별을 1번... 이런 식으로 쌍을 맞추면 된다.

또 수학적인 표현도 기억하기.

parent=[i for i in range(n+2)]
stars = [list(map(float, sys.stdin.readline().split())) for _ in range(n)]
# stars 에 [[1.0, 1.0], [1.0, 2.0], [2.0, 4.0]]과 같이 넣고 iteration 할 때 0번, 1번 이런식으로 빼니까
#그런 index 값도 같이 heap push하면 된다.

for i in range(len(stars)):
  for j in range(len(stars)):
    if i==j: #자기자신은 넘어간다
      continue
    p1 = stars[i]
    p2 = stars[j]
    # 제곱과 제곱근, 소수점 2째짜리까지 round하기
    w = round(((p1[0]-p2[0])**2+abs(p1[1]-p2[1])**2)**0.5, 2)
    heapq.heappush(edges, (w,p1,p2,i,j))

 

3. 구현

import sys
import heapq

sys.stdin = open("input.txt")

n = int(sys.stdin.readline())
edges=[]
parent=[i for i in range(n+2)]
stars = [list(map(float, sys.stdin.readline().split())) for _ in range(n)]

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

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

for i in range(len(stars)):
  for j in range(len(stars)):
    if i==j:
      continue
    p1 = stars[i]
    p2 = stars[j]
    w = round(((p1[0]-p2[0])**2+abs(p1[1]-p2[1])**2)**0.5, 2)
    heapq.heappush(edges, (w,p1,p2,i,j))

answer=0
while edges:
  w,s,e,i,j = heapq.heappop(edges)
  if find(i, parent)!=find(j, parent):
    uni(i,j, parent)
    answer+=w

print(answer)