백준 1647번 도시분할 계획

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

1647번: 도시 분할 계획

기본적인 최소신장트리 문제와는 달리 마을을 두개로 분할해야하는 조건이 있는 문제이다.

최소신장트리 알고리즘으로 모든 마을을 연결하는 최소비용의 경로를 구해준 후 가장 비용이 높은 간선을 제거해주면 마을을 최소비용으로 2개로 분할하게 된다.

import sys
input = sys.stdin.readline

def find_parent(parent,x):

    if parent[x] != x:
        parent[x] = find_parent(parent,parent[x])
    return parent[x]

def union_parent(parent, a,b):
    a = find_parent(parent,a)
    b = find_parent(parent,b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b

v, e = map(int, input().split())
parent = [0] * (v+1)

edges = []
result = []

for _ in range(e):
    a, b, cost = map(int,input().split())
    edges.append((cost,a,b))

for i in range(1, v+1):
    parent[i] = i

edges.sort()

for edge in edges:
    cost, a, b = edge

    if find_parent(parent,a) != find_parent(parent,b):
        union_parent(parent,a,b)
        # cost를 기록
        result.append(cost)

tmp = sum(result)
print(tmp - sorted(result)[-1])

최소신장트리 기본 알고리즘 출처 : https://www.youtube.com/watch?v=aOhhNFTIeFI&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=8