[Baekjoon] 1774번 : 우주신과의 교감 (Python, 최소 신장 트리)

[Baekjoon] 1774번 : 우주신과의 교감 (Python, 최소 신장 트리)

 

목차

 

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

1774번: 우주신과의 교감

코드 링크

https://github.com/stellaluminary/Baekjoon

GitHub - stellaluminary/Baekjoon

Python

 

방법 1 - 메모리 107516KB / 시간 2076ms / 코드 길이 778B

 

기존 최소 신장 트리와 같다.

여러 우주신(노드)가 존재하고 cost가 적은 교신(edge)을 구하는 것이다.

다만 큰 차이점이라고 한다면 m개에 대하여 이미 특정 노드와 통로가 뚤려있다는 것이다.

이 부분을 고려한 코드를 구현하면 다음과 같다. 

 

import sys
input = sys.stdin.readline

def f_p(p, x):
    if p[x] != x:
        p[x] = f_p(p, p[x])
    return p[x]

def union(p, a, b):
    a, b = f_p(p, a), f_p(p, b)
    p[max(a,b)] = min(a,b)

def dist(c1, c2):
    return ((c1[0] - c2[0])**2 + (c1[1] - c2[1])**2)**0.5

n, m = map(int, input().split())

p = [i for i in range(n+1)]

coord, edges = [], []
res = 0

for i in range(n):
    x, y = map(int, input().split())
    coord.append((x,y))

for j in range(m):
    a, b = map(int, input().split())
    union(p, a, b)

for i in range(n-1):
    for j in range(i+1, n):
        edges.append((dist(coord[i], coord[j]), i+1, j+1))

edges.sort()

for edge in edges:
    c, a, b = edge
    if f_p(p, a) != f_p(p, b):
        union(p, a, b)
        res += c

print('%.2f' %(res))