[백준][4386][Python 파이썬][G3] 별자리 만들기

문제

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

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

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

입력

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

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

출력

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

 

테스트케이스

3 1.0 1.0 2.0 2.0 2.0 4.0	6 4 1 5 8 2 1 8 4 2 9 1 4	5 1 7 3 2 9 10 48 23 5 90	9 1 1 1 2 1 3 2 1 2 2 2 3 3 1 3 2 3 3
3.41	18.32	134.65	8.00

 

코드

import sys

input = sys.stdin.readline

N = int(input())

roots = [*range(N+1)]

stars = []

for i in range(N):

    stars.append([*map(float, input().split())])

links = []

for i in range(N-1):

    for j in range(i+1, N):

        links.append([i+1, j+1, ((stars[j][0]-stars[i][0])**2 +

                     (stars[j][1]-stars[i][1])**2)**(0.5)])

links.sort(key=lambda x: x[2])

def findroot(a):

    while a != roots[a]:

        a = roots[a]

    return a

def merge(a, b):

    aroot = findroot(a)

    broot = findroot(b)

    if aroot != broot:

        if aroot > broot:

            roots[aroot] = broot

        else:

            roots[broot] = aroot

        return True

    return False

idx = 0

cnt = 1

ans = 0

while cnt < N:

    s, e, cost = links[idx]

    if merge(s, e):

        cnt += 1

        ans += cost

    idx += 1

print(ans)

 

후기

처음엔 링크를 안줘서 어 크루스칼로 안되나? 프림 써야되나? 싶었는데

어차피 프림을 써도 그때 가서 또 점들 안이어진거 잔뜩 찾아서,, 넣어서 최소부터 돌리고.. 이상하다 싶어서 보니까 N이 최대 100밖에 안됐다

그냥 링크 다만들어서 넣고 풀면 간단한 최소스패닝트리문제