1197 최소 스패닝 트리 (Python)

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

 

import sys
input = sys.stdin.readline

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

Edges = []

for _ in range(E):
    A, B, C = map(int, input().split())
    Edges.append([A, B, C])

def third_val(e):
    return(e[2])

Edges.sort(key = third_val)

# 각 정점이 들어있는 유니온을 기록함
union = [i for i in range(V)]

def kruskal(edge):
    s = union[edge[0]-1]
    e = union[edge[1]-1]

    if s == e:
        return 0
    else:
        for i in range(V):
            if union[i] == s:
                union[i] = e
        return edge[2]

result = 0
for edge in Edges:
    result += kruskal(edge)
print(result)

 

각 정점이 속해있는 유니온을 숫자로 추상화해서 풀었다.

리스트를 딕셔너리로 바꾼다던가 하면 더 빨라질듯?
지금은 유니온을 정점 개수만큼 선언한 뒤에 매번 훑어서 좀 느리다.