[ 16398 ] [ Kruskal ] 행성 연결

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

16398번: 행성 연결

---

풀이 과정

---

1. Kruskal 알고리즘을 사용하여 최소 비용 신장 트리를 구성한다.
   1. 최소 비용인 간선을 하나 선택하고 Cycle을 형성하는지 체크한다
   2. Cycle을 형성하는지 체크하는 방법은 간선에 연결된 두 점이 하나의 집합에 속해있는지 확인하면 된다.
      1. Union-find 알고리즘 사용
   3. Cycle을 형성하지 않는다면 두 점을 연결해 주고 비용을 더해준다.
   4. 위 과정을 총 N-1개의 간선을 선택할 때까지 반복해 준다.
2. 최소 비용 신장 트리의 비용의 합계를 출력시켜 준다.

---

풀이 과정

---

import sys
import heapq

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

N = int(input())
heap = []
cost = [list(map(int,input().split())) for _ in range(N)]

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

def union(parent, a, b):
    p1 = find(parent, a)
    p2 = find(parent, b)
    if p1 != p2:
        parent[p1] = p2

for i in range(N):
    for j in range(i+1, N):
        heapq.heappush(heap, [cost[i][j], i, j])

answer = 0
parent = [i for i in range(N+1)]
edge_count = 0
while heap and edge_count < N-1:
    cost, fr, to = heapq.heappop(heap)
    if find(parent, fr) != find(parent, to):
        union(parent, fr, to)
        answer += cost
        edge_count += 1


print(answer)