1774_우주신과의 교감

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

1774번: 우주신과의 교감

 

 

이전 문제와 비슷하게 풀 수 있다.

 

1. 각좌표 받기

2. 연결되어 있는부분 노드 받기

3. 각 노드들간 거리를 계산해놓는 배열 만들기

 

[ (1,2,거리), (1,3,거리),(1,4,거리).... (n-1,n,거리) ]

로 만들어야 한다. 이때 1번 부터 시작인걸 생각하고 만들어야 한다.

 

4. 배열을 거리순으로 오름차순 정렬 ( 가까운 순서대로 )

5. 부모 배열 만들기 (트리구조 이용)

6. 미리 이어져 있는 부분 같은 트리로 만들어주기

7. 만든 거리배열을 다 순회하면서 최소 가중치로 트리 만들어주기

 

import sys
input = sys.stdin.readline

n,m = map(int,input().split())
position = []
for _ in range(n):
    x,y = map(int,input().split())
    position.append((x,y))
path = []
for _ in range(m):
    a,b = map(int,input().split())
    path.append((a,b))
dist = []

for i in range(n):
    for j in range(i+1,n):
        distance = (( position[i][0] - position[j][0] )**2 + (position[i][1] - position[j][1]) **2)**0.5
        dist.append((i+1,j+1,distance))
dist.sort(key=lambda x:x[2])

parents=[i for i in range(n+1)]
def find(a):
    if parents[a] == a:
        return a
    parents[a] = find(parents[a])
    return parents[a]
def union(a,b):
    a,b = find(a),find(b)
    if a > b:
        parents[a] = b
    else:
        parents[b] = a
result = 0
for a,b in path:
    union(a,b)

for a,b,c in dist:
    if find(a) != find(b):
        union(a,b)
        result += c

print('%.2f'%result)