[ 1774 ] [ Kruskal ] 우주신과의 교감

 

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

1774번: 우주신과의 교감

 

---

풀이 과정

---

1. 입력받은 우주신들의 좌표를 사용하여 서로 다른 우주신들 사이의 거리를 모두 구해서 최소히프에 넣어준다.
   • (1->2, 1->3, ..., N-1->N)
   • 최소 히프에는 거리 기준으로 최소 히프에 넣을거기 때문에 (거리, 시작점, 끝점) 순으로 넣어준다. 
2. 미리 연결된 우주신들에 대해서는 Union 연산을 미리 해준다.
3. 이후 히프에서 하나씩 꺼내면서 연결된 점이 같은 집합에 속해있는지 검사한다.(find) 속해있지 않다면 해당 간선을 사용해야 하므로 union 연산을 해주고, 거리는 따로 더해둔다.
4. 따로 더해둔 거리를 출력시켜 준다.

같은 kruskal 알고리즘을 사용하더라도 응용해야 되는 문제들이 풀기가 좀 어렵다. 이번 문제에서는 간선 정보가 주어지지 않고, 푸는 사람이 직접 만들어야 했기 때문에 더 그랬던 것 같음.

---

소스 코드

---

 

import sys
import heapq
import math

input = lambda: sys.stdin.readline().rstrip()

N, M = map(int, input().split())

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

    if parent[pa] != parent[pb]:
        parent[pa] = parent[pb]

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

    return parent[a]

pos = [[0, 0]]

parent = [i for i in range(N+1)]

for _ in range(1, N+1):
    x, y = map(int, input().split())
    pos.append([x, y])

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

heap = []

for i in range(1, N+1):
    for j in range(1, i):
        distance = math.sqrt((pos[i][0] - pos[j][0]) ** 2 + (pos[i][1] - pos[j][1]) ** 2)
        heapq.heappush(heap, [distance, i, j])

answer = 0
while heap:
    dist, i, j = heapq.heappop(heap)
    if find(parent, i) != find(parent, j):
        answer += dist
        union(parent, i, j)
    else:
        continue

print("%.2f"%answer)