[백준] [크루스칼 알고리즘] [union-find] 1647. 도시 분할 계획

최소 스패닝 트리는 하나의 그래프에서

1. 모든 노드를 포함하면서
2. 사이클이 존재하지 않는 부분 그래프이며
3. 가중치의 합이 최소인

그래프이다. 그리고 이 최소 스패닝 트리에 관한 알고리즘으로는 크루스칼 알고리즘이 있다.

크루스칼 알고리즘은 그래프에서 A와 B를 선택했을 때 A에서 B로 가는 경로가 반드시 존재하도록 최소 비용으로 간선을 배치하는  경우의 수에 관한 알고리즘이다. 이 알고리즘의 지향점은 당연히 최소 스패닝 트리를 만족하면서 가중치의 합이 최소가 되게끔 하는 것이다.

 

일반적인 크루스칼 알고리즘의 기본 코드와 상당히 유사하다. 비용과 시작점, 끝점을 각 정점으로 두는 edges 배열에 넣고 반복문을 돌면서 조상 노드가 같지 않은 경우, 즉 그 시작점과 끝점이 연결되어있지 않은 경우 두개를 합친 다음 그 인덱스에 해당하는 비용을 result라는 배열에 넣는 방식이다.

 

도시를 두개로 나누는데 나눈 그 두 도시가 모두 비용의 합이 최소가 되려면, 크루스칼 알고리즘을 통해 구현한 최소 스패닝 트리 전체의 가중치 중에서 가장 큰 값을 빼주면 된다. 가장 큰 값을 빼줄 경우 자연스럽게 최소 스패닝 트리의 성질을 잃고 두 개로 나뉘게 된다. 하지만 두 도시 모두 가중치의 합이 최소인 상태가 된다.

 

즉 마을들끼리를 연결하고 있는 다리 중 가장 가중치가 큰 다리를 두 도시를 나누는 기준으로 삼고 잘라버리면 되는 것이다.

 

• 다른 사람 풀이
  • 유지비 합을 최소로 하기 위해 정렬해줘야함
  • 가중치가 제일 큰 값을 빼는 것: 가장 가중치가 큰 길을 없애는 것

#n개의 집, m개 간선, 가중치 o 
#마을이 서로 연결되도록 분할

n,m=map(int,input().split())
load=[]
for i in range(m):
    s,e,v=map(int,input().split())
    load.append((s,e,v))
load.sort(key=lambda x:x[2])

root=[i for i in range(n+1)]
def union(x,y):
    xroot=find(x)
    yroot=find(y)
    if xroot<yroot:
        root[yroot]=xroot
    else:
        root[xroot]=yroot

def find(x):
    if root[x]!=x:
        root[x]=find(root[x])
    return root[x]

result=0
last=0
for ld in load:
    s,e,v=ld
    if find(s)!=find(e):
        union(s,e)
        result+=v
        last=v

print(result-last)