[Python] 백준 1774번 - 우주신과의 교감

📖 문제

1774번: 우주신과의 교감

 

🔎 풀이

유니온 파인드를 활용하는 최소 신장 트리 문제입니다. 백준 4386번 별자리 만들기 문제와 비슷합니다. 다른 점은 이미 연결되어 있는 간선이 존재한다는 것입니다. 이미 연결된 통로들은 길이 합에 넣어줄 필요가 없습니다. 따라서 길이를 계산하기 전에, 연결된 통로들의 root를 통합하여 줍니다. root를 통합하기 위해서는 미리 구현한 union 함수를 이용하면 됩니다.

 

아래 코드에서는 우주신이 1번이 아닌 0번부터 있다고 가정하였습니다.

 

💻 코드

import sys
input = sys.stdin.readline

# root를 찾는 함수
def find_parents(x):
    if parents[x] == x:
        return x
    return find_parents(parents[x])

# root를 통합하는 함수
def union_parents(a, b):
    a = find_parents(a)
    b = find_parents(b)
    if a < b:
        parents[b] = a
    else:
        parents[a] = b

# 두 점 사이의 거리를 계산하는 함수
def cal_dist(x1, y1, x2, y2):
    return ((x1 - x2) ** 2 + (y1 - y2) ** 2) ** 0.5


N, M = map(int, input().split())
parents = [int(x) for x in range(N)]
graph = []

for _ in range(N):
    x, y = map(int, input().split())
    graph.append((x, y))

# 이미 연결된 통로들의 root 합치기
for _ in range(M):
    a, b = map(int, input().split())
    union_parents(a-1, b-1)

ans = 0
dist = []

for i in range(N):
    for j in range(i+1, N):
        # 통로 거리 계산
        cost = cal_dist(graph[i][0], graph[i][1], graph[j][0], graph[j][1])
        dist.append((cost, i, j))

# 최소 거리 순으로 나열
dist.sort()
for k, i, j in dist:
    # 두 별의 root가 같지 않다면 거리비용 추가하고 root 합치기
    if find_parents(i) != find_parents(j):
        union_parents(i, j)
        ans += k

print(f'{ans:.2f}')