1922: 네트워크 연결

문제 링크

1922: 네트워크 연결

구현 방식

• kruskal 알고리즘으로 MST를 구해주었다
  • MST: cycle이 발생하지 않고, 간선들의 가중치 합이 가장 작은 tree
  • kruskal 알고리즘을 이용하기 위해선 edges를 weight 기준으로 오름차순 정렬해줘야함

코드

import sys

def find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])
    return parent[x]

def union(a, b):
    a = find(a); b = find(b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b

N = int(sys.stdin.readline()[:-1]); M = int(sys.stdin.readline()[:-1])
edges = []
for m in range(M):
    a, b, c = map(int, sys.stdin.readline()[:-1].split())
    edges.append((a, b, c))
edges.sort(key=lambda x:x[2]) #weight를 기준으로 오름차순 정렬 (Kruskal)

parent = [n for n in range(N+1)]

tc = 0
for u, v, c in edges:
    if find(u) != find(v): #root노드가 같지 않다면 신장트리에 추가
        tc += c
        union(u, v)
print(tc)