BOJ 1922 - 네트워크 연결

문제

백준 온라인 저지 - 1922번

풀이 과정

모든 컴퓨터를 연결하는 네트워크를 구성하는 최소 비용을 구하는 문제입니다.
크루스칼 알고리즘 을 이용해서 MST 를 구현했으며 union 연산에서는 랭크 최적화와 경로 압축을 사용했습니다.

코드

import sys


def union(v1, v2):
    r1, r2 = find(v1), find(v2)
    if r1 == r2:
        return

    if rank[r1] > rank[r2]:
        parent[r2] = r1
    else:
        parent[r1] = r2
        if rank[r1] == rank[r2]:
            rank[r2] += 1


def find(v):
    if parent[v] != v:
        parent[v] = find(parent[v])

    return parent[v]


def kruskal():
    total_cost = 0

    for v in range(1, N + 1):
        parent[v] = v
        rank[v] = 0

    for frm, to, cost in sorted(edges, key=lambda edge: edge[2]):
        r1, r2 = find(frm), find(to)
        if r1 != r2:
            union(r1, r2)
            total_cost += cost

    return total_cost


def solution():
    answer = kruskal()

    return answer


if __name__ == '__main__':
    N = int(input())
    M = int(input())
    edges = [list(map(int, sys.stdin.readline().split())) for _ in range(M)]
    parent = [-1] * (N + 1)
    rank = [0] * (N + 1)

    answer = solution()
    print(answer)