[Python] 백준 4386번: 별자리 만들기

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

4386번: 별자리 만들기

 

import sys
import math
import itertools
input = sys.stdin.readline


def getDistance(p1, p2):
    return math.sqrt(((p1[0] - p2[0])**2 + (p1[1] - p2[1])**2))


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

    px = find(parent[x])
    parent[x] = px
    return px


def union(x, y):
    px, py = find(x), find(y)

    if px > py:
        parent[px] = py
    else:
        parent[py] = px


if __name__ == '__main__':
    # 입력
    N = int(input())
    stars = [list(map(float, input().split())) for _ in range(N)]

    # For union-find
    parent = [i for i in range(N)]

    # For kruskal
    sets = []
    for i1, i2 in itertools.combinations(parent, 2):
        sets.append([i1, i2, getDistance(stars[i1], stars[i2])])

    # 거리에 대해 오름차순 정렬
    sets.sort(key=lambda x: x[2])

    # Kruskal
    minCost = 0
    for i1, i2, d in sets:
        if find(i1) != find(i2):
            union(i1, i2)
            minCost += d

    # 출력
    print("{:.2f}".format(minCost))

 

 

Kruskal 알고리즘을 사용하면 된다. 기존 크루스칼에서 어떠한 변형이 없으므로 자세한 설명은 아래 링크로 대체한다.

 

https://rccode.tistory.com/entry/Python-%EB%B0%B1%EC%A4%80-1197%EB%B2%88-%EC%B5%9C%EC%86%8C-%EC%8A%A4%ED%8C%A8%EB%8B%9D-%ED%8A%B8%EB%A6%AC

[Python] 백준 1197번: 최소 스패닝 트리