백준 4386 : 별자리 만들기 (Python)

본문 링크

📌 크루스칼 알고리즘

"""
간선이 없기 때문에 모든 정점들 사이의 거리를 구해준다.
"""
import sys
input=sys.stdin.readline

def Find(x):

    if x!=disjoint[x]:
        disjoint[x]=Find(disjoint[x])
    return disjoint[x]

N=int(input())
disjoint=[ i for i in range(N+1) ]

star=[]
edge=[]
for i in range(N):
    x,y=map(float,input().split())
    star.append((x,y))

for i in range(N-1):
    for j in range(i+1,N):
        edge.append((i,j, ((star[i][0]-star[j][0])**2+(star[i][1]-star[j][1])**2)**0.5))

edge.sort(key=lambda x:x[2])

total=0

for x,y,value in edge:

    x=Find(x)
    y=Find(y)

    if x!=y:
        if x>y:
            disjoint[x]=y
        else:
            disjoint[y]=x
        total+=value

print("%.2f"%total)

📌 프림 알고리즘

import sys,heapq
input=sys.stdin.readline

N=int(input())
star=[tuple(map(float,input().split())) for _ in range(N) ]

Tree=[ [] for _ in range(N+1) ]

for i in range(N):
    for j in range(N):
        if i==j: #트리는 양방향이기때문에 같은 지점을 연결하는것만 빼고 모두 연결해준다.
            continue
        Tree[i].append((j,((star[i][0]-star[j][0])**2+(star[i][1]-star[j][1])**2)**0.5))

visit=[False]*(N+1)
heap=[(0,0)]
total=0

while heap:

    value,node=heapq.heappop(heap)

    if not visit[node]:
        visit[node]=True
        total+=value

        for i,j in Tree[node]:
            heapq.heappush(heap,(j,i))

print("%.2f"%total)

📌 어떻게 접근할 것인가?

최소 스패닝 트리 문제입니다.

문제에서 별자리들의 $X$ , $Y$ 좌표만 주어졌기 때문에 먼저 모든 노드들 사이의 거리를 구해준 다음에
크루스칼 알고리즘과 프림 알고리즘을 사용하여 풀었습니다.