[PS] BOJ 1647 도시 분할 계획

문제 링크

문제 정리)
마을을 두 개로 분리하고자 하는데 각 마을의 집들은 모두 연결되어 있다.
필요없는 길은 모두 없애고 남은 길의 유지비 합을 최소로 만들어라!

앞에서 푼 네트워크 연결 문제와 비슷하게 풀면 된다.
한 가지 차이점이 있다면 이번엔 마을을 2개로 분리한다는 점이다.

마을의 집들을 최소신장트리를 만족하도록 모두 연결한 다음 가장 비용이 큰 길만 삭제하면 된다.

그럼 마을은 두 개로 분리되면서, 남은 길들의 유지비 합은 최소가 된다.

---

n, m = map(int, input().split())
parent = list(range(n + 1))
edges = []
result = 0

def find_parent(x):
    if parent[x] != x:
        parent[x] = find_parent(parent[x])
    return parent[x]
    
def union(a, b):
    a = find_parent(a)
    b = find_parent(b)
    
    if a < b:
        parent[b] = a
    else:
        parent[a] = b
        
for _ in range(m):
    a, b, c = map(int, input().split())
    edges.append((a, b, c))
    
edges.sort(key = lambda x:x[2]) # 비용을 기준으로 정렬

for i in range(m):
    a, b, c = edges[i]
    if find_parent(a) == find_parent(b):
        continue
    union(a, b)
    result += c
    last = c
    
print(result - last)

네트워크 연결 velog 코드에서 마지막 부분만 수정하면 된다.