난이도

Gold 4

문제

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

별자리를 이루는 선은 서로 다른 두 별을 일직선으로 이은 형태이다. 모든 별들은 별자리 위의 선을 통해 서로 직/간접적으로 이어져 있어야 한다. 별들이 2차원 평면 위에 놓여 있다. 선을 하나 이을 때마다 두 별 사이의 거리만큼의 비용이 든다고 할 때, 별자리를 만드는 최소 비용을 구하시오.

입력

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

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

출력

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

예제 입력

예제 출력

3.41

해설 및 후기

부쩍 최소 스패닝 트리 문제를 자주 접하는데, 이 문제 역시 비슷한 문제였다. 대신 각 간선의 가중치가 직접적으로 주어지진 않는다. 그래서 먼저 O(N^2)의 시간 복잡도 정도로 각 좌표마다의 간선을 임의로 만들어 가중치를 만든 후(n이 1000이라 충분하다), 만들어진 간선에 최소 스패닝 트리를 적용한다. UNION-FIND를 활용한다.

제출 코드

import sys
n = int(sys.stdin.readline().rstrip())

l = []
for i in range(n):
    l.append(list(map(float,sys.stdin.readline().rstrip().split())))

roads = []

for i in range(n):
    targetX, targetY = l[i]
    for j in range(i+1,n):
        destX, destY = l[j]
        roads.append([i,j,((destX-targetX)**2 + (destY-targetY)**2)**0.5])

roads.sort(key=lambda x:x[2])
parent = [i for i in range(n)]

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

def union(x,y):
    pX = find(x)
    pY = find(y)
    if(pX < pY):
        parent[pY] = pX
    else:
        parent[pX] = pY

cnt = 0
val = 0

for a,b,value in roads:
    if(cnt == n-1):
        break
    if(find(a) != find(b)):
        union(a,b)
        cnt += 1
        val += value

print(round(val,2))