1197: 최소 스패닝 트리

풀이 시간

• 7m
• 사실 사전에 "17472: 다리만들기 2" 문제를 먼저 풀었다

구현 방식

1. edges에 대해 cost 기준으로 오름차순 정렬
2. edge를 하나씩 확인하며 현재의 edge가 node들 간에 사이클을 발생시키는 지 확인
3. 사이클이 발생하지 않으면 MST에 포함 / 사이클이 발생하면 MST에 포함시키지 않음
4. 2~3번 과정을 모든 edge에 대해 수행

코드

import sys

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, sys.stdin.readline()[:-1].split())
edges = []
for e in range(E):
    A, B, C = map(int, sys.stdin.readline()[:-1].split())
    edges.append((A, B, C))
edges.sort(key=lambda x:x[2])

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

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

결과