백준 1774번 : 우주신과의 교감 in Python

1774번: 우주신과의 교감

 

www.acmicpc.net

이 문제는 이전의 별자리 만들기 문제와 유사하나 이미 연결된 정점이 있다는 조건이 추가되었다.

백준 4386번 : 별자리 만들기 in Python

4386번: 별자리 만들기 www.acmicpc.net 이 문제는 2차원 평면 위의 별들을 이용해 별자리를 만들 때 선으로 연결된 별들의 거리의 합의 최소값을 구하는 문제이다. 즉, 이 문제는 최소 스패닝 트리를 구하는 문제..

wanna-be-developer-yjh.tistory.com

그러므로 위 문제의 풀이와 크게 차이는 없으나 Kruskal's algorithm을 수행하기 전에 이미 연결된 정점을 연결해주기 위해 union 함수를 적용한다. 단, 입력으로 이미 연결된 정점이 주어질 때 번호가 좌표들의 순서이므로 1부터 시작하지만, 코드 내에서는 번호가 0부터 시작하므로 이를 반영해서 코드를 작성해야 한다.

그리고 소수점 둘째 자리까지 출력해야 하는데, 이를 위해서 round 함수를 사용했더니 계속 틀렸다. 알고 보니 round 함수는 반올림한 결과를 반환하지 소수점 둘째 자리까지 나타내는 것은 아니기 때문에 이를 명확히 출력하려면 round 함수가 아닌 format 함수를 이용해야 한다.

이를 코드로 구현하면 다음과 같다.

import sys
import math
import heapq
input = sys.stdin.readline
sys.setrecursionlimit(10**5)

def find(u):
    if parent[u] == u: return u
    parent[u] = find(parent[u])
    return parent[u]
def union(u, v):
    root_u = find(u)
    root_v = find(v)
    parent[root_u] = root_v
N, M = map(int, input().split())
parent = [i for i in range(N+1)]
space_gods = []
heap = []
for _ in range(N):
    x, y = map(int, input().split())
    space_gods.append([x, y])
# 이미 연결된 정점들은 union 함수를 이용해 연결한다.
for i in range(M):
    a, b = map(int, input().split())
    if find(a-1) != find(b-1):
        union(a-1, b-1)
for i in range(N):
    for j in range(i+1, N):
        dis = math.sqrt((space_gods[i][0] - space_gods[j][0])**2 + (space_gods[i][1] - space_gods[j][1])**2)
        heapq.heappush(heap, [dis, i, j])
W = 0
while len(heap) > 0:
    w, u, v = heapq.heappop(heap)
    if find(u) != find(v):
        union(u, v)
        W += w
print(format(W, ".2f"))