BaekJoon 1774번 : 우주신과의 교감 (python)

BaekJoon 1774번 : 우주신과의 교감 (G3 30.827%)

우주신과의 교감 문제

크루스칼 알고리즘을 이용한 MST 문제이다.

• 문제에서 주어지는 조건에서 M개의 줄은 이미 연결되어 있는 통로이기 때문에 해당 root들은 거리 계산을 하기전에 먼저 union을 해주어 루트를 통일시켜놓고 한 부분집합으로 만들어준다.
• 모든 우주신들의 좌표들의 거리를 계산하여 튜플로 묶어주고 거리를 오름차순으로 정렬한 뒤 크루스칼 알고리즘을 이용해 루트 노드가 같지않은 노드들을 통일시켜주고 거리들을 더해준다.

---

import sys,math
input = sys.stdin.readline

def find(x) :
    if root[x] != x:
        root[x] = find(root[x])
    return root[x]

def union(x,y) :
    rootX = find(x)
    rootY = find(y)
    if rootX > rootY :
        root[rootY] = rootX
    else :
        root[rootX] = rootY

N, M = map(int,input().split())
root = list(i for i in range(N+1))

edges = list()
for _ in range(N) :
    a, b = map(int,input().split())
    edges.append((a,b))

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

distance = list()
for i in range(N) :
    for j in range(i+1, N) :
        dis = math.sqrt((edges[i][0] - edges[j][0])**2 + (edges[i][1] - edges[j][1])**2)
        distance.append((dis,i,j))
distance.sort()

result = 0
for i in distance :
    dis, x, y = i[0],i[1],i[2]
    if find(x) != find(y) :
        union(x,y)
        result += dis

print('%.2f'%result)

---