[Baekjoon 1197] 최소 스패닝 트리

문제

💛Ⅳ [Baekjoon 1197 - 최소 스패닝 트리]

문제 풀이 방법

최소 스패닝 트리를 구하는 알고리즘은 크루스칼 알고리즘을 이용하여 구할 수 있다!

1. 간선 데이터를 비용에 따라 오름차순으로 정렬한다.
2. 간선을 하나씩 확인하며 현재의 간선이 사이클을 발생시키는지 확인한다.
   1. 사이클이 발생하지 않는 경우, 최소 신장 트리에 포함시키며 그 때의 비용을 계산한다.
   2. 사이클을 발생하는 경우, 최소 신장 트리에 포함시키지 않는다.
3. 모든 간선에 대하여 2번 과정을 반복한다.

풀이 코드

Python

import sys
input = sys.stdin.readline

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

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

v, e = map(int,input().split())
edges = [list(map(int, input().split())) for _ in range(e)]
parent = [i for i in range(v+1)]

edges.sort(key=lambda x:x[2])

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

print(result)