# BOJ - 4386 - 별자리 만들기

Updated:

```
import sys
import math
import heapq
def PRIM(graph, V, idx):
hq = []
visit = [False] * (V + 1)
visit[idx] = True
distance = 0
cnt = 1
for i in graph[idx]:
heapq.heappush(hq, i)
while hq:
weight, vertex = heapq.heappop(hq)
if not visit[vertex]:
visit[vertex] = True
cnt += 1
distance += weight
for i in graph[vertex]:
heapq.heappush(hq, i)
if cnt == V:
return distance
return -1
def getDistance(x1, x2):
return (
math.sqrt(math.pow(x1[0] - x2[0], 2) + math.pow(x1[1] - x2[1], 2))
)
def solution():
N = int(sys.stdin.readline())
vertex = []
graph = [[] for _ in range(N)]
for idx in range(N):
x, y = map(float, sys.stdin.readline().split())
vertex.append([x, y])
for i in range(N):
for j in range(i + 1, N):
distance = getDistance(vertex[i], vertex[j])
graph[i].append([distance, j])
graph[j].append([distance, i])
print("%0.2f"%PRIM(graph, N, 0))
solution()
```

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

## Leave a comment