백준 1197: 최소 스패닝 트리 (Python)

 

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

1197번: 최소 스패닝 트리

 

일반적인 크루스칼 알고리즘으로 풀면 된다.

1. 간선 -> 비용 기준 오름차순 정렬

2. 사이클이 발생하지 않으면(= parent가 같지 않으면) union

 

한번 에러났었는데,,, 어이없게도 cost 기준으로 정렬한다는 생각에 사로잡혀서

간선에 대한 정보 a, b, c를 입력 받을 때 c, a, b로 입력받음,,ㅎ 실수하지 말자

 

import sys
sys.setrecursionlimit(10000)
input = sys.stdin.readline

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

def union(parent, a, b):
    a = find(parent, a)
    b = find(parent, b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b

v, e = map(int, input().split())

parent = [0] * (v+1)
for i in range(1, v+1):
    parent[i] = i

edges = []
for _ in range(e):
    a, b, c = map(int, input().split())
    edges.append((c, a, b))
edges.sort()

res = 0

for i in edges:
    c, a, b = i
    if find(parent, a) != find(parent, b):
        union(parent, a, b)
        res += c

print(res)