알고리즘 기초 - 크루스칼 알고리즘(최소 신장 트리)

반응형

- 크루스칼(Kruskal) 알고리즘이란?

크루스칼 알고리즘에 대해 설명하기 전, 서로소 집합 연산과 신장 트리에 대해 알아야 합니다! 그럼 각각에 대한 개념을 설명하겠습니다.

​

1) 서로소 집합

서로소 집합이란! 수학적 의미 그대로 공통 원소가 없는 두 집합을 의미합니다. 두 개의 집합이 주어졌을 때 겹치는 요소들이 하나도 없어야 합니다. 두 집합이 서로소인지 판별하는 알고리즘은 다음과 같습니다.

1. 합집합 연산(union)을 통해 서로 연결된 두 노드 A와 B를 확인합니다.

=> A와 B의 루트 노드 A'과 B'을 각각 찾습니다.

=> A'를 B'의 부모 노드로 설정해줍니다.

2. 모든 합집합 연산을 처리할 때까지 1번 과정을 계속 반복해줍니다.

이 서로소 집합 연산을 이용한다면 무방향 그래프에서의 사이클 존재여부를 판별할 수 있습니다. 그래프 내의 간선을 확인하던 중 두 노드를 확인했을 때 두 노드의 루트 노드가 서로 같다면 사이클이 발생한 것이라고 판단할 수 있습니다.

​

​

2) 신장트리

신장 트리란! 하나의 그래프가 있을 때 그래프 내의 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 의미합니다. 이때, 모든 노드를 최소한의 비용으로 연결한 것이 최소 신장 트리이며, 이 트리의 존재 여부와 루트를 찾을 수 있도록 해주는 것이 바로 크루스칼 알고리즘입니다. 알고리즘의 작동 과정은 다음과 같습니다.

1. 간선 테이블 비용에 따라 오름차순으로 정렬합니다.

2. 간선을 하나씩 확인하면서 현재의 간선을 포함했을 시 사이클이 발생하는지 확인합니다.

=> 사이클 X : 최소 신장 트리에 포함해줍니다.

=> 사이클 O : 최소 신장 트리에 포함 하지 않습니다.

3. 모든 간선에 대해 2번과정을 반복해줍니다.

 

 

백준 알고리즘 1197번: 최소 스패닝 트리 문제를 이용해 코드를 구현해보겠습니다.

문제 링크: https://www.acmicpc.net/problem/1197

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)
edges = []
result = 0
for i in range(1, v+1):
    parent[i] = i

for _ in range(e):
    a, b, c = map(int, input().split())
    edges.append((c, a, b)) ## 비용순 정렬

edges.sort()
for edge in edges:
    c, a, b = edge
    if find_parent(parent, a) != find_parent(parent, b):
        union_parent(parent, a, b)
        result += c
print(result)