백준 1774 우주신과의 교감

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

1774번: 우주신과의 교감

백준 4386번 문제와 같은 유형의 문제이다.

이번에는 n이 1000개라 2중 for문을 돌리면 시간초과가 나오지 않을까 싶었는데 다행이도 2중 for문으로 통과가 되었다.

중간에 이미 연결된 우주신의 좌표들은 입력받자마자 union_find 해버리면 최소비용계산때 알아서 계산대상에서 제외가 된다.

import math
import sys
input = sys.stdin.readline

def find_parent(parent,x):
    if parent[x] != x:
        parent[x] = find_parent(parent,parent[x])
    return parent[x]

def union_parent(parent, a,b):
    a = find_parent(parent,a)
    b = find_parent(parent,b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b

v, e = map(int, input().split())
parent = [0] * (v+1)

edges = []
result = 0

for i in range(1, v+1):
    parent[i] = i

tmp_list = []
# 우주 신들의 좌표
for _ in range(v):
    a,b = map(float,input().split())
    tmp_list.append((a,b))

# 이미 연결되어 있는 우주신들의 index
for _ in range(e):
    a,b = map(int,input().split())
    # 입력 받자마자 union_find 실시
    union_parent(parent,a,b)

# 우주신들의 거리 계산
for idx1, j in enumerate(tmp_list):
    for idx2, k in enumerate(tmp_list):
        if idx1 == idx2:
            continue

        tmp_cost = (j[0] - k[0])**2 + (j[1] - k[1])**2
        tmp_cost = math.sqrt(tmp_cost)
        edges.append((tmp_cost,idx1+1,idx2+1))

edges.sort()

# 최소 비용 계산
for edge in edges:
    cost, a, b = edge

    if find_parent(parent,a) != find_parent(parent,b):
        union_parent(parent,a,b)
        result += cost

print(f"{result:.2f}")