[백준] 1922. 네트워크 연결 - Python

[Gold IV]

 

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

1922번: 네트워크 연결

 

풀이

기본적인 MST(Minimum Spanning Tree) 문제.

Kruskal 알고리즘을 통해 MST를 구현하였다.

응용된 것 없이 MST를 구현하기만 하면 되는 문제이므로 설명은 생략.

 

AC.

from collections import deque

# input
N = int(input())
M = int(input())
root = {i: i for i in range(1, N+1)}
edges = []
for _ in range(M):
    a, b, c = map(int, input().split())
    edges.append([c, a, b])

# Union-Find
def find(x):
    if root[x] == x:
        return x
    root[x] = find(root[x])
    return root[x]

def union(x, y):
    rx = find(x)
    ry = find(y)
    if rx < ry:
        root[ry] = rx
    else:
        root[rx] = ry
        
# MST
edges = sorted(edges)
result = 0
for cost, a, b in edges:
    if find(a) == find(b):
        continue
    
    union(a, b)
    result += cost
    
print(result)