[백준] 1647 - 도시 분할 계획(Minimum Spanning Tree)

import sys
input = sys.stdin.readline
 
n, m = map(int, input().split())
parent = [i for i in range(n + 1)]
edges = list()
 
 
def find_parent(c):
    if parent[c] != c:
        parent[c] = find_parent(parent[c])
    return parent[c]
 
 
def union(a, b):
    ap, bp = find_parent(a), find_parent(b)
    if ap < bp:
        parent[bp] = ap
    else:
        parent[ap] = bp
 
 
for _ in range(m):
    a, b, c = map(int, input().split())
    edges.append((c, a, b))
edges.sort()
 
cost = 0
for edge in edges:
    c, a, b = edge
    if find_parent(a) != find_parent(b):
        last = c
        cost += c
        union(a, b)
print(cost - last)

https://www.acmicpc.net/problem/1647

1647번: 도시 분할 계획

간단한 MST 문제이다.

주의할 점은, 도시를 둘로 나눈다고 했으니 MST의 가장 비용이 비싼 간선은 제외해서 연결을 끊어야한다. (n - 2개의 간선만 연결)