[이것이 코딩테스트다] 신장 트리 + 크루스칼 알고리즘

신장 트리와 크루스칼 알고리즘이란 것을 많이 들어는 봤는데 자주 까먹어서 정리해놓으려고 한다.

 

신장 트리란 ?

 하나의 그래프가 있을 때 모든 노드를 포함하면서, 사이클이 존재하지 않는 부분 그래프를 의미한다.

따라서 다음과 같이 하나의 그래프에 대한 여러가지 신장 트리가 존재한다.

 

 

 

 

크루스칼 알고리즘이란?

알고리즘 문제를 풀다보면 최소한의 비용으로 신장 트리를 찾는 문제를 많이 봤을 것이다.

예를 들어 도시 사이에 도로를 놓아 전체 도시가 서로 연결될 수 있도록 하려고 할 때 최소 비용을 구하는 문제.

크루스칼 알고리즘의 순서는 이러하다.

 

1.모든 간선에 대하여 오름차순으로 정렬

 

2.간선을 순차적으로 확인하며 사이클 체크

2-1. 사이클이 발생하지 않는 경우 최소 신장 트리에 포함

2-2. 사이클이 발생하는 경우 포함시키지 않고 다음 간선 체크

 

3.모든 간선에 대하여 반복

 

서로소 집합에서 사용하던 union-find를 이용한 코드는 다음과 같다.

#크루스칼 알고리즘

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

    return parent[x]

def union_parent(parent,a,b):
    a = find_parent(parent,a)
    b = find_parent(parent,b)

    if a < b :
        parent[b] = a
    else :
        parent[a] = b
v,e = map(int,input().split())    
parent = [0] * (v+1)
for i in range(1,v+1):
    parent[i] = i

edges = []
res = 0

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

edges.sort()

for edge in edges :
    cost,a,b = edge
    if find_parent(parent,a) != find_parent(parent,b):
        union_parent(parent,a,b)
        res += cost

print(res)

 

크루스칼 알고리즘의 시간 복잡도

간선의 개수가 E개 일 때 시간 복잡도는 O(ElogE)이다.

시간이 가장 오래 걸리는 부분이 정렬 작업을 할 때라서!