[백준] 1197. 최소 스패닝 트리 - 파이썬

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

1197번: 최소 스패닝 트리

 

[참고] 이 블로그.. 알고리즘 설명 맛집이다! 깔끔하고 최고.

MST(Minimum Spanning Tree)

MST(Minimum Spanning Tree) - Kruskal 알고리즘

Union-Find 알고리즘

 

풀이

MST(Minimum Spanning Tree, 최소 스패닝 트리, 최소 신장 트리)의 기본 문제.

MST를 구현하는 방법에는 Kruskal(크루스칼) 알고리즘, Prim(프림) 알고리즘 두 개정도가 주로 이용되는데,

Kruskal 알고리즘은 Edge(간선)이 적은 문제에 적합, Prim 알고리즘은 Edge가 많은 문제에 적합하므로,

이 문제에서는 Kruskal 알고리즘으로 구현하였다.

 

V, E = map(int, input().split())
edges = []

'''간선 정보 입력 (V1, V2, Edge's cost)'''
for _ in range(E):
    edges.append(list(map(int, input().split())))

'''Union-Find 구현'''
root = dict()
for i in range(1, V+1):
    root[i] = i

def find(x):
    if root[x] == x:
        return x
    else:
        root[x] = find(root[x])
        return root[x]

def union(x, y):
    x = find(x)
    y = find(y)

    root[y] = x

'''Kruskal 이용'''
'''Edge cost 오름차순으로 정렬'''
edges = sorted(edges, key=lambda x: x[2])

total_cost = 0

for edge in edges:
    '''사이클이 만들어지는 edge라면 pass.'''
    if find(edge[0]) == find(edge[1]):
        continue
    else:
        total_cost += edge[2]
        union(edge[0], edge[1])

print(total_cost)