백준 1774 [우주신과의 교감] 파이썬

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

 

# 백준 1774 우주신과 교감
# 최소 스패닝 트리(MST, Kruskal 알고리즘) 활용
# - N개의 좌표(우주신)와 M개의 이미 연결된 통로가 주어짐
# - 나머지를 최소 비용으로 연결하는 거리 합 구하기

import sys
import math
input = sys.stdin.readline

N, M = map(int, input().split())  # N = 우주신 수, M = 이미 연결된 통로 수
ans = 0                           # 최종 결과(연결 비용 합)
pos = [[0, 0]]                    # 1-based indexing을 위해 더미 좌표 추가

# 유니온-파인드 parent 초기화
parent = [i for i in range(N + 1)]

def find(x):
    """루트 노드 찾기 (경로 압축 적용)"""
    if x != parent[x]:
        parent[x] = find(parent[x])
    return parent[x]

def union(a, b):
    """두 노드를 합치기 (사이클 방지)"""
    a = find(a)
    b = find(b)
    if a != b:             # 다른 집합일 때만 합침
        parent[a] = b
        return True
    return False

# 1. 좌표 입력 받기
for _ in range(N):
    pos.append(list(map(int, input().split())))

# 2. 이미 연결된 M개의 간선 union 처리
for _ in range(M):
    A, B = map(int, input().split())
    union(A, B)

# 3. 모든 가능한 간선(거리) 계산
costs = []
for i in range(1, N + 1):
    for j in range(i + 1, N + 1):   # i < j로 최적화 가능 (중복 제거)
        pos_i_x, pos_i_y = pos[i]
        pos_j_x, pos_j_y = pos[j]
        cost = math.sqrt((pos_i_x - pos_j_x) ** 2 + (pos_i_y - pos_j_y) ** 2)
        costs.append((i, j, cost))

# 4. 거리 기준으로 간선 정렬
costs.sort(key=lambda x: x[2])

# 5. 크루스칼 알고리즘 실행
for a, b, c in costs:
    if union(a, b):     # 연결되지 않은 노드라면 MST에 포함
        ans += c

# 6. 결과 출력 (소수점 둘째 자리까지)
print("{:.2f}".format(ans))

마지막에 소수점 둘째 자리까지 출력이 생각이 안났다..

그 외에는 무난한 MST 문제