[백준/BOJ/알고리즘/파이썬(python)]#1197_최소 스패닝 트리[MST/트리/그래프]

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

1197번: 최소 스패닝 트리

MST 문제를 풀어보려고 했는데 다 다이아몬드 문제 뿐이라.. 골드 문제를 찾아서 풀어보았다.

 

스패닝 트리(Spanning Tree)란 1. 모든 정점을 포함하고 2. 사이클(Cycle)이 존재하지 않는 트리다.

최소 스패닝 트리(Minimum Spanning Tree_MST)는 3. 가중치가 최소 되는 트리다. 

 

크루스칼 알고리즘(Kruskal Algorithm)을 이용하여 풀었다.

크루스칼 알고리즘은 다이나믹 프로그래밍(DP)를 이용하며 최솟값을 계속해서 선택하는 그리디 알고리즘이다. 

 

백준 문제에서 제시된 예제를 트리로 시각화하면 이렇게 된다. 

#입력 예제
3 3
1 2 1
2 3 2
1 3 3

보라색 하이라이팅이 크루스칼 알고리즘으로 찾아낸 가중치 최소화된 순회 방법이다. 

#출력(답)
3

프림 알고리즘으로 MST를 구하는 방법도 있는데 다음에 기회가 된다면 다루어보고 싶다.

 

 

파이썬 코드 

#1197 MST
import sys
input = sys.stdin.readline

V, E = map(int, input().split())

kruskal = []
for i in range(E):
    a, b, w = map(int, input().split())
    kruskal.append((a,b,w))

kruskal.sort(key=lambda x: x[2]) #sort by weight

parent = [i for i in range(V+1)]

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


weight_sum=0
for a,b,w in kruskal:

    if find(a)!=find(b):
        
        a = find(a)
        b = find(b)

        if a > b:
            parent[a] = b
        else:
            parent[b] = a

        weight_sum += w

print(weight_sum)