악곱 == 악성곱슬

크루스칼, 최소 신장 트리

---

본 문제는 최소 신장 트리를 구하는 프로그램을 작성하는 문제이다. 최소 신장 트리를 찾도록 구현하는 방법에는 Prim, Kruskal 두 가지 알고리즘이 대표적으로 존재한다.

두 알고리즘에 대해 간략하게 비교하자면, Kruskal 알고리즘은 간선의 개수가 적을때 유용하다. 간선을 정렬하여 그리디하게 가장 적은 비용의 간선부터 고르는 방법이다. Prim 알고리즘은 간선의 개수가 많을 때 유용하며, 우선순위 큐를 이용하여 매 노드에서 가장 비용이 적은 간선을 골라가며 찾는 방식이다. Prim알고리즘은 다익스트라와 매우 유사하다.

본 문제는 간선의 개수가 최대 10만개이므로 sort()메서드를 사용해도 시간복잡도에서 문제가 없기 때문에 간단하게 Kruskal 알고리즘을 이용하여 구현한 코드이다.

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

def solution(v, e):
    parent = [0] * (v + 1)
    edges = []
    result = 0

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

    for _ in range(e):
        a, b, c = map(int, sys.stdin.readline().rstrip().split())
        edges.append((c, a, b))

    edges.sort()

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

    return result

if __name__ == "__main__":
    V, E = map(int, sys.stdin.readline().rstrip().split())
    print(solution(V, E))