백준 1197 최소 스패닝 트리 (파이썬)

28 May 2021 in Dev on BOJ

1197 최소 스패닝 트리 바로가기

접근방식

최소 신장 트리 카테고리 문제로 크루스칼 알고리즘 을 이용하여 풀었다.

파이썬 코드

import sys

v, e = map(int, sys.stdin.readline().split())
arr = []
for _ in range(e):
    a, b, c = map(int, sys.stdin.readline().split())
    arr.append((c,a,b))

# 크루스칼 알고리즘은 정렬이 필요!
arr.sort(key=lambda x: x[0])
parent = list(range(v + 1))

#유니온 파인드 연산
def union(a, b):
    a = find(a)
    b = find(b)

    if b < a:
        parent[a] = b
    else:
        parent[b] = a
def find(a):
    if a == parent[a]:
        return a
    parent[a] = find(parent[a])  # 경로 압축
    return parent[a]

sum = 0
for c, a, b in arr:
    if find(a) != find(b):
        union(a, b)
        sum += c

print(sum)