[백준] 1774번 우주신과의 교감 - 파이썬(Python)

문제 (링크)

 

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

1774번: 우주신과의 교감

 

나의 풀이

import sys
input = sys.stdin.readline

def get_dist(loc1, loc2):
    x1, y1, x2, y2 = loc1[0], loc1[1], loc2[0], loc2[1]
    return ((x1 - x2) ** 2 + (y1 - y2) ** 2) ** 0.5


def find(parent, x):
    if x != parent[x]:
        parent[x] = find(parent, parent[x])

    return parent[x]


def union(parent, a, b):
    a = find(parent, a)
    b = find(parent, b)

    if a < b:
        parent[b] = a
    
    else:
        parent[a] = b


N, M = map(int, input().split())
parent = list(range(N+1))

edges = [0] * (N+1)
for i in range(1, N+1):
    edges[i] = list(map(int, input().split()))


for _ in range(M):
    a, b = map(int, input().split())
    union(parent, a, b)


possible = []
for i in range(1, len(edges)-1):
    for j in range(i+1, len(edges)):
        possible.append([get_dist(edges[i], edges[j]), i, j])


possible.sort()
ans = 0

for p in possible:
    cost, x, y = p[0], p[1], p[2]

    if find(parent, x) != find(parent, y):
        union(parent, x, y)
        ans += cost
    
print("{:.2f}".format(ans))

# step
# M개를 먼저 연결 (Union)
# 만들 수 있는 연결들을 dist와 함께 저장
# Kruskal

 

풀이법 및 코드설명

크루스칼 알고리즘을 통해 해결할 수 있는 문제이다.

 

이미 연결된 M개의 통로를 먼저 Union해주고, 모든 노드들에 대하여 연결 가능한 조합을 해당 조합의 거리와 함께 possible 리스트에 담아준다.

 

이를 거리를 기준으로 오름차순 정리해주고, 크루스칼 알고리즘을 사용해 연결해주며, 새로 연결되는 선분의 거리를 ans에 더해준다.