[백준 1197번 | 골드4] 최소 스패닝 트리

2년전 알고리즘 수업에서 배웠던 최소 스패닝 트리.. 코드로 구현하기는 사실상 처음.

 

스패닝트리는 G(V, E)그래프가 주어졌을 때 사이클을 피해 V-1개의 간선을 가지고 트리를 만들면 된다.

최소 스패닝트리는 그저 간선 가중치들의 합이 최소가 되게 하면 된다.

 

대표적으로 프림, 크루스칼이 있는데 난 크루스칼 방식을 택했다.

크루스칼 방식은 사이클을 만들지 않는 범위에서 최소 비용의 '간선'을 하나씩 더해가는 방식이다.

개념 자체는 어렵지 않다고 생각한다.

1. 모든 간선을 가중치 크기 순으로 정렬

2. 사이클이 생성되지 않는 선에서 간선 추가

이 두가지를 수행하면 되는데 사이클이 생성되지 않게 하려면 집합을 이용해야 한다.

 

그런데 아무리 생각해도 집합 하나로는 힘들고, '여러개면 어떻게 관리하지?'라는 생각만 들었다.

전에 공부했던 알고리즘 책도 한 번 보고, 인터넷을 뒤지다가 'Union-Find' 알고리즘을 사용하게 되었다.

Union-Find를 활용해 트리처럼 다루게 된다면 위의 문제는 해결된다.

import sys
# 간선들을 가중치로 정렬
# 간선을 값이 적은 것부터 추가
# 추가할 때 정점을 고려해서 추가
# 만약 추가하는 정점 두 개가 같은 집합에 속해 있으면 그건 사이클을 만드니 추방

input = sys.stdin.readline
n, m  = map(int, input().split())

li = [] #간선관리 리스트
for i in range(m):
    li.append(list(map(int, input().split())))
li = sorted(li, key = lambda x:-x[2])

parent = [i for i in range(n+1)]#정점 set

def get_parent(x): #부모찾기
    if parent[x]==x:
        return x
    parent[x] = get_parent(parent[x])
    return parent[x]

def union_parent(p, q):#작은놈이 부모가 되도록 Union
    p = get_parent(p)
    q = get_parent(q)

    if p>q:
        parent[p] = q
    else:
        parent[q] = p
def same_parent(p, q):
    return get_parent(p) == get_parent(q)

l=0
k=0
while l<n-1:
    a, b, c = li.pop()
    if not same_parent(a,b):#두 정점이 다른 집합이면
        k+=c
        union_parent(a, b)#한 집합이 되도록 Union
        l+=1
print(k)