[Python] BOJ / 4386번 / 별자리 만들기

4386번: 별자리 만들기

 

문제

도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다.

• 별자리를 이루는 선은 서로 다른 두 별을 일직선으로 이은 형태이다.
• 모든 별들은 별자리 위의 선을 통해 서로 직/간접적으로 이어져 있어야 한다.

별들이 2차원 평면 위에 놓여 있다. 선을 하나 이을 때마다 두 별 사이의 거리만큼의 비용이 든다고 할 때, 별자리를 만드는 최소 비용을 구하시오.

입력

첫째 줄에 별의 개수 n이 주어진다. (1 ≤ n ≤ 100)

둘째 줄부터 n개의 줄에 걸쳐 각 별의 x, y좌표가 실수 형태로 주어지며, 최대 소수점 둘째자리까지 주어진다. 좌표는 1000을 넘지 않는 양의 실수이다.

출력

첫째 줄에 정답을 출력한다. 절대/상대 오차는 10-2까지 허용한다.

풀이

2차원 평면 상에 있는 모든 별들을 연결하는 최소 비용을 구하는 문제로 최소 스패닝 트리 알고리즘을 사용하였습니다.

 

우선 모든 별 사이의 거리를 계산하여 배열에 저장해놓은 뒤 해당 배열을 오름차순 정렬하고, 크루스칼 알고리즘을 수행하여 출력값에 두 별 사이의 거리를 지속적으로 더해주었습니다.

---

from math import sqrt
import sys

# 전처리 부분
input = sys.stdin.readline

def get_distance(x, y, xx, yy):
    dx = pow((x - xx), 2)
    dy = pow((y - yy), 2)

    return sqrt(dx + dy)

# 알고리즘 부분
def find_parent(x):
    if parent[x] != x:
        parent[x] = find_parent(parent[x])
    return parent[x]

def union_parent(a, b):
    a = find_parent(a)
    b = find_parent(b)

    if a != b:
        parent[a] = b

def kruskal():
    ans = 0

    for d, a, b in stars:
        if find_parent(a) != find_parent(b):
            union_parent(a, b)
            ans += d

    print(round(ans, 2))

# 변수 선언 및 초기화 부분
n = int(input())
points = []
for _ in range(n):
    x, y = map(float, input().split())
    points.append([x, y])
parent = [0] * n
for i in range(n):
    parent[i] = i
stars = []

# 메인 코드 부분
for i in range(n):
    x = points[i][0]
    y = points[i][1]

    for j in range(i + 1, n):
        xx = points[j][0]
        yy = points[j][1]

        dist = get_distance(x, y, xx, yy)
        stars.append([dist, i, j])

stars.sort()
kruskal()