백준 1922 네트워크 연결

문제

네트워크 연결

컴퓨터를 연결하는데 드는 최소 비용을 구하자

난이도 : Gold4

---

풀이

1. kruskal을 이용해 mst를 만들고 최소 cost를 구한다.

---

코드

import sys

n = int(sys.stdin.readline())
m = int(sys.stdin.readline())
data = [tuple(map(int, sys.stdin.readline().split())) for _ in range(m)]

parent = [0] * (n+1)
for i in range(1, n+1):
    parent[i] = i
edges = sorted(data, key=lambda x:x[-1])  # 맨 마지막 정보가 cost이므로 마지막 원소를 기준으로 sort

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

def union(a, b, parent):
    x = find(a, parent)
    y = find(b, parent)
    
    if x < y:
        parent[y] = x
    else:
        parent[x] = y
        
def kruskal():
    total = 0
    tree = []
    for i in range(m):
        a, b, cost = edges[i]
        if find(a, parent) != find(b, parent):
            union(a, b, parent)
            total += cost
 
    print(total)
            
kruskal()

        

---

결과

union-find 및 kruskal을 이용한 기본 문제였다.