[최소 신장 트리/Python] 1197번: 최소 스패닝 트리 - 효과는 굉장했다!

1197번: 최소 스패닝 트리

 

알고리즘 분류

• 그래프 이론
• 최소 스패닝 트리

 

 

SOLUTION

import sys

# 크루스칼 알고리즘 사용하여 최소 가중치를 구한다
def find(parent, x):
    if parent[x] != x:
        parent[x] = find(parent, parent[x])

    return parent[x] 


def union(parent, A, B):
    root_A = find(parent, A)
    root_B = find(parent, B)

    if root_A < root_B:
        parent[root_B] = root_A
         
    else:
        parent[root_A] = root_B


V, E = map(int, sys.stdin.readline().split())

parent = [i for i in range(V+1)] # 부모 테이블 초기화
nodes = []
result = 0

for _ in range(E):
    A, B, cost = map(int, sys.stdin.readline().split())
    nodes.append((cost, A, B))

# cost가 작은 순으로 정렬
nodes.sort()

for i in range(E):
    cost, A, B = nodes[i]
    # find 함수 실행시, 부모노드가 다르면 union 함수 수행 
    if find(parent, A) != find(parent, B):
        union(parent, A, B)
        result += cost
        
print(result)