[Python] 네트워크 연결 - 백준 (MST)

해당 글은 백준 1922번 문제 '네트워크 연결'을 다룬다.

문제

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

1922번: 네트워크 연결

 

설명

해당 문제는 최소 신장트리를 구하는 MST 문제이다.

아래의 코드를 크루스칼 알고리즘을 사용하여 작성하였다.

* graph에 간선을 저장할 때, 비용을 앞에 적어서 바로 정렬할 수 있도록 하였다.

 

코드

n = int(input())
m = int(input())

parent = [0]*(n+1)
for i in range(n+1):
    parent[i] = i

graph = []
for _ in range(m):
    a, b, c = map(int, input().split())
    graph.append((c, a, b))

graph.sort()

def find_parent(parent, x):
    if parent[x] != x:
        parent[x] = find_parent(parent, parent[x])
    return parent[x]

def union_parent(parent, x, y):
    a = find_parent(parent, x)
    b = find_parent(parent, y)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b

result = 0
for edge in graph:
    c, a, b = edge
    if find_parent(parent, a) != find_parent(parent, b):
        union_parent(parent, a, b)
        result += c

print(result)