BaekJoon 4386번 : 별자리 만들기 (python)

BaekJoon 4386번 : 별자리 만들기 (G3 58.423%)

별자리 만들기 문제

크루스칼 알고리즘을 응용한 문제이다.

• 해당 문제에서는 가중치가 거리라는 것을 알고는 있지만 입력을 받을 때 가중치를 따로 입력받지 않아서 헷갈릴 수도 있는 문제이다.
• 문제의 조건이 n이 100이하이기 때문에 조건이 널널하기 때문에 각 점에서 모든 점까지의 거리를 계산하여 해당 거리에 대하여 오름차순으로 정렬하고 간선의 길이가 가장 짧은 순서대로 부분집합을 만들어가기 시작한다.
• 그렇게 만들어진 부분집합은 모든 노드들을 최소한의 가중치로 전부 다 잇는 부분집합이 된다.

import sys,math
input = sys.stdin.readline

def find(x) :
    if root[x] != x :
        root[x] = find(root[x])
    return root[x]

def union(x,y) :
    rootX = find(x)
    rootY = find(y)
    if rootX > rootY :
        root[rootY] = rootX
    else :
        root[rootX] = rootY

n = int(input())

root = list(i for i in range(n+1))
stars = list()
edge = list()
result = 0
for _ in range(n) :
    a, b = map(float, input().split())
    stars.append((a,b))

for i in range(len(stars)) :
    for j in range(i+1, len(stars)) :
        dis = math.sqrt((stars[j][0] - stars[i][0])**2 + (stars[j][1] - stars[i][1])**2)
        edge.append((dis,i,j))

edge.sort()

for i in edge :
    cost, a, b = i[0], i[1], i[2]
    if find(a) != find(b) :
        union(a,b)
        result += cost

print(round(result,2))