BOJ 1197 - 최소 스패닝 트리

문제

백준 온라인 저지 - 1197번

풀이 과정

최소 스패닝 트리 를 구하는 문제입니다.
기본 문제이기 때문에 별도로 복잡한 로직이 추가되지는 않았습니다.
오랜만에 MST 문제를 한번 풀어보고 싶어서 가장 기본이 되는 문제를 한번 풀어봤습니다. 😄

코드

import sys


def union(u, v):
    pu, pv = find(u), find(v)

    if pu != pv:
        if rank[pu] > rank[pv]:
            parent[pv] = pu
        else:
            parent[pu] = pv
            if rank[pu] == rank[pv]:
                rank[pv] += 1


def find(u):
    if parent[u] == u:
        return u

    parent[u] = find(parent[u])

    return parent[u]


def solution():
    acc = 0

    edges.sort(key=lambda edge: edge[2])

    for frm, to, weight in edges:
        if find(frm) != find(to):
            union(frm, to)
            acc += weight

    return acc


if __name__ == '__main__':
    V, E = list(map(int, sys.stdin.readline().split()))
    edges = [list(map(int, sys.stdin.readline().split())) for _ in range(E)]

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

    answer = solution()

    print(answer)