January 21, 2023

1197번: 최소 스패닝 트리

문제 요약

• 정점의 갯수 V와 간선이 주어졌을 때, MST의 가중치를 출력
• 1 ≤ V ≤ 10,000, 1 ≤ E ≤ 10,000

풀이

from sys import stdin

input = stdin.readline

V, E = map(int, input().split())
edge_list = [list(map(int, input().split())) for _ in range(E)]
parent_list = [i for i in range(V + 1)]
result = 0

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

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

def union_parent(parent_list, a, b):
    a = find_parent(parent_list, a)
    b = find_parent(parent_list, b)

    if (a < b):
        parent_list[b] = a
    else:
        parent_list[a] = b

for edge in edge_list:
    start, end, cost = edge
    parent_start = find_parent(parent_list, start)
    parent_end = find_parent(parent_list, end)

    if (parent_start != parent_end):
        union_parent(parent_list, parent_start, parent_end)
        result += cost

print(result)

• Kruskal 알고리즘과 Disjoint Set을 이용

시간 복잡도 분석

• Kruskal 알고리즘은 간선의 정렬 시간에 의존
• $ElogE$