백준 4386번 별자리 만들기 파이썬

문제

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

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

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

입력

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

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

출력

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

예제 입력 1

3
1.0 1.0
2.0 2.0
2.0 4.0

예제 출력 1

3.41

제출 답안

import sys
input = sys.stdin.readline
def parent_find(x):
    if x == parent[x]:
        return x
    else:
        return parent_find(parent[x])
def union_parent(a, b):
    root_a, root_b = parent_find(a), parent_find(b)
    parent[root_b] = root_a
 
 
N = int(input())
stars = [list(map(float, input().split())) for _ in range(N)]
parent = [_ for _ in range(N)]
costs = {}
 
for i in range(N):
    for j in range(i + 1, N):
        a = stars[i]
        b = stars[j]
        dist = round(((a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2) ** 0.5, 2)
        costs[(i, j)] = dist
 
 
costs = sorted(costs.items(), key=lambda x: x[1])
 
 
 
answer = 0
while costs:
    current = costs.pop(0)
    a, b = current[0]
    cost = current[1]
 
    if parent_find(a) != parent_find(b):
        answer += cost
        union_parent(a, b)
 
print(answer)

1. 부모를 찾을 수 있는 함수와 부모를 찾은 후 합치는 함수를 만든다.
2. 별자리 값을 입력받고 N만큼의 부모리스트와 비용을 담을 딕셔너리를 만든다.
3. 0부터 하나씩 뒤로 나가아가면서 거리를 계산한다.
   1. 점과 점사이의 거리를 계산하며 해당 인덱스의 딕셔너리에 담는다.
4. value값을 오름차순으로 정렬한다.
5. 그다음에 딕셔너리에서 하나씩 빼면서 별자리가 이어진거마다 부모가 다르면 거리를 더하고 부모가 같게 해준다.