[크루스칼 알고리즘] 1647번

링크 - https://www.acmicpc.net/problem/1647

코드

import sys
input = sys.stdin.readline

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

def union(parent,a,b):
    a= find_parent(parent, a)
    b = find_parent(parent,b)
    if a<b:
        parent[b]=a
    else:
        parent[a]=b
        
n,m = map(int,input().split())

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

edges=[]
result=0

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

#간선을 오름차순으로 정렬
edges.sort()

cross=0

#크루스칼 실행
for edge in edges:
    cost, a, b= edge
    if find_parent(parent,a)!=find_parent(parent,b):
        union(parent,a,b)
        result+=cost
        cross=cost

print(result-cross)

집들을 연결하는 경로들 중에서 최소한의 경로만 남겨두고 나머지는 없앤다고 한다. -> 최소신장트리를 찾는 문제이므로 크루스칼 알고리즘을 사용하면 된다.

이 때, 최소한의 경로로 집을 이어주고, 마을을 2개의 마을로 분할한다고 한다. -> 2개의 최소신장트리를 만들어줘야 한다.

하나의 최소신장트리를 만들고 중간에 길 하나를 없애버리면 2개의 트리가 만들어진다. 이 때 최소한의 비용을 사용한다고 했으므로 가장 마지막에 연결한 길을 없애주면 된다.(cross변수)