[Python] 별자리 만들기 - 백준 (MST)

해당 글은 백준 4386번 '별자리 만들기' 문제를 다룬다.

문제

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

4386번: 별자리 만들기

 

설명

해당 문제는 최소 신장 트리를 구하는 알고리즘으로 해결할 수 있다.

여기서는 크루스칼 알고리즘을 사용하였고, graph에 두 점 사이의 거리를 저장하고, 오름차순으로 정렬한 후 계산하였다

 

코드

import math
n = int(input())
point = []
for _ in range(n):
    x, y = map(float, input().split())
    point.append((x, y))
graph = []
for i in range(n):
    for j in range(i+1, n):
        dist = math.sqrt((point[i][0]-point[j][0])**2 + (point[i][1]-point[j][1])**2)
        graph.append((dist, i+1, j+1))
graph.sort()

parent = [0]*(n+1)
for i in range(n+1):
    parent[i] = i

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

def union_parent(parent, x, y):
    a = find_parent(parent, x)
    b = find_parent(parent, y)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b

result = 0
for edge in graph:
    c, a, b = edge
    if find_parent(parent, a) != find_parent(parent, b):
        union_parent(parent, a, b)
        result += c

print(result)