문제 정리)
마을을 두 개로 분리하고자 하는데 각 마을의 집들은 모두 연결되어 있다.
필요없는 길은 모두 없애고 남은 길의 유지비 합을 최소로 만들어라!
앞에서 푼 네트워크 연결 문제와 비슷하게 풀면 된다.
한 가지 차이점이 있다면 이번엔 마을을 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 코드에서 마지막 부분만 수정하면 된다.