[baekjoon] 네트워크 연결

링크텍스트

모두가 자료를 공유하기 위해서는 모든 컴퓨터가 연결되어 있어야 하고, 이왕이면 컴퓨터 연결 비용을 최소로 하여야 한다. 각 컴퓨터를 연결하는데 필요한 비용이 주어졌을 때 모든 컴퓨터를 연결하는데 필요한 최소비용을 출력하라.

전형적인 최소신장트리의 가중치의 합을 구하는 문제이다.

크루스칼 알고리즘을 통해 풀 수 있다.

# 네트워크 연결
n = int(input())    # 컴퓨터의 수(노드)
m = int(input())    # 연결할 수 있는 선의 수(엣지)
computer = []
for _ in range(m):
    a, b, c = list(map(int, (input().split())))
    computer.append((c, a, b))  # a, b, cost
    
parent = [i for i in range(n+1)]
# 최소 비용. 즉, 최소 신장 트리
# find parent
def find(x):
    if x != parent[x]:
        parent[x] = find(parent[x])
    return parent[x]

# union parent
def union(a, b):
    a = find(a)
    b = find(b)
    
    if a < b:
        # 작은 쪽으로 합침
        parent[b] = a
    else:
        parent[a] = b
        
def kruskal():
    computer.sort()
    cost_sum = 0
    used_edges = 0
    for cost, a, b in computer:
        if find(a) != find(b):
            if used_edges == n-1: break  # 노드수-1
            union(a, b)
            cost_sum += cost
            used_edges += 1
    return cost_sum

print(kruskal())