이번에 저희 스터디는 크루스칼 알고리즘 / 프림 알고리즘에 대해서 공부했습니다.
그래프에서 최소 신장 트리(Minimum Spanning Tree)를 찾을 수 있는 알고리즘이 존재합니다.
일단, 신장 트리라는 것은 그래프 내에서 모든 정점들을 연결하고 사이클이 없는 그래프입니다.
그래서 최소 신장 트리는 각 간선이 가지고 있는 가중치의 합이 최소가 되는 신장 트리를 말합니다.
이 최소 신장 트리는 N개의 정점을 가지는 그래프에 대해 반드시 N-1개의 간선만을 가져야 합니다.
이러한 최소 신장 트리를 구하는 알고리즘은 다음과 같습니다.
-
크루스칼(Kruskal) 알고리즘 : 그리디 알고리즘 기반으로 모든 간선에 대해 가중치가 적은 간선부터 연결하면서 만들어 나가는 알고리즘입니다. 이때, 가중치가 적은 간선부터 연결하는데, 연결하는 도중 사이클이 발생하게 되면 가중치가 적은 간선이라도 무시해야 합니다.
-
프림(Prim) 알고리즘 : 시작 정점에서부터 출발해서 신장 트리 집합을 확장해 나가는 방법입니다. 크루스칼 알고리즘은 간선을 기준으로 하지만 이 프림 알고리즘은 정점을 기준으로 합니다.
크루스칼 알고리즘의 동작 과정만 설명하겠으며, 그 과정은 다음과 같습니다.
-
그래프 간선의 가중치를 기준으로 오름차순으로 정렬합니다.
-
정렬된 간선 리스트에서 순서대로 사이클을 형성하지 않는 간선을 선택합니다. 가장 낮은 가중치를 선택하며, 사이클을 형성하는 간선은 제외합니다.
-
해당 간선을 현재의 최소 신장 트리의 집합에 추가합니다.
여기서 중요한 점은 사이클을 어떻게 판단할 수 있을까요?
바로 Union - Find라는 자료구조를 사용합니다.
이 Union - Find는 서로소 집합을 표현하는 자료구조입니다.
Union - Find에는 서로 다른 두 집합을 합치는 Union 연산과 집합 원소가 어떤 집합에 속해있는지 찾는 Find 연산으로 구성되어 있습니다.
사이클이 발생하는 경우는 같은 그래프에 속한 두 노드를 연결했을 때이기 때문에 이러한 Union - Find의 개념을 이용해서 판단할 수 있습니다.
대략적인 Union - Find의 동작 방식은 다음과 같습니다.
-
정점의 개수만큼 부모(Parent) 테이블을 초기화합니다. 이때, 초기 값은 자기 자신을 부모로 가지도록 설정합니다.
-
Union연산으로 두 노드 사이를 합칩니다. 여기서 합칠 때, 일반적으로 더 작은 값 쪽으로 부모노드하고 합칩니다. -
만약, 2번에서 연결된 두 노드 사이에서 또 다른 노드가 연결된다면,
Find연산으로 부모노드를 계속 찾습니다. 이때,재귀함수가 사용됩니다.
위에서 설명한 것을 토대로 크루스칼 알고리즘으로 최소 신장 트리를 구하는 것을 백준 1197번 - 최소 스패닝 트리 문제에서 기본을 다질 수 있습니다.
이 문제를 Python으로 구현하면 다음과 같습니다.
Python
import sys
# Union - Find
def union(x, y):
v1 = find(x)
v2 = find(y)
if v1 < v2: # v2의 부모 노드 번호가 크다면
parent[v2] = v1 # v2의 부모 노드를 v1로 변환
else:
parent[v1] = v2
def find(x):
if parent[x] != x: # 자기 자신이 부모 노드가 아니면
parent[x] = find(parent[x]) # 부모 노드 탐색
return parent[x] # 부모 노드 반환
# 정점의 개수와 간선의 개수 입력
v, e = map(int, sys.stdin.readline().split())
graph = []
# 각 간선에 대한 정보 입력
for _ in range(e):
a, b, c = map(int, sys.stdin.readline().split())
graph.append((c, a, b))
# 부모 리스트 초기화
parent = [i for i in range(v+1)]
# 간선 비용을 기준으로 오름차순 정렬
graph.sort()
answer = 0
# 크루스칼 알고리즘
for i in range(e):
c, a, b = graph[i]
if find(a) != find(b): # 부모노드가 다르면 사이클이 발생하지 않기 때문에, union 수행
union(a, b)
answer += c # 간선 비용 추가
print(answer)이상으로 이번 주에는 크루스칼/프림 알고리즘에 대해서 공부하고 기본적인 크루스칼 알고리즘 문제를 풀었습니다.
