크루스칼 알고리즘이란?
크루스칼 알고리즘은 최소 신장 트리(MST, Minimum Spanning Tree)를 찾는 대표적인 알고리즘 중 하나로, 다음과 같은 특징이 있다.
- 간선을 하나씩 추가하면서 MST를 만들어 간다.
- 탐욕적 기법(Greedy Algorithm)을 사용한다.
- 시간 복잡도는 O(E log V)
크루스칼 알고리즘 과정
초기 상태로 정점는 서로 연결되어 있지 않다.
간선을 하나씩 추가하면서 최소 신장 트리(MST)를 만든다.
크루스칼 알고리즘을 수행하고 완성된 그래프는 최소 신장 트리이다.
간선을 추가하는 방식은 다음과 같다.
- 모든 간선을 가중치 기준으로 오름차순 정렬한다.
- 가중치가 작은 간선부터 하나씩 선택하여 MST에 추가한다.
- 사이클이 발생하는지 확인한다.
- 사이클이 생기지 않으면 해당 간선을 MST에 포함한다.
- 사이클이 발생하면 해당 간선을 제외한다.
- 모든 정점이 연결될 때까지 위 과정을 반복한다.
👉 여기서, 사이클 판별을 위해 유니온 파인드(Union-Find) 알고리즘을 사용한다.
정점 V와 정점 W를 연결하는 간선 E를 선택할 때,
V와 W의 루트 노드가 같다면(이미 같은 집합에 속해 있다면) 사이클 발생 → 간선 추가 X
루트 노드가 다르면 서로 다른 집합 → 간선 추가 O
유니온 파인드 알고리즘 알아보기
🔗 https://wikidocs.net/206632
크루스칼 알고리즘 예제 문제
📌 프로그래머스 섬 연결하기 [level 3]
문제 설명
여러 개의 섬이 주어지고, 각 섬을 연결하는 다리를 건설하는 비용이 주어진다.
모든 섬을 연결하는 데 필요한 최소 비용을 구하는 문제이다.
✨ 크루스칼 알고리즘 적용 과정
- 다리 건설 비용을 기준으로 간선들을 오름차순 정렬한다.
- 사이클이 발생하지 않도록 하나씩 간선을 추가한다.
- (정점 개수 - 1)개의 간선을 선택하면 종료한다.
| 단계 | 선택된 간선 | 총 비용 |
|---|---|---|
| 1 | (0-1) 비용 1 | 1 |
| 2 | (1-3) 비용 1 | 2 |
| 3 | (0-2) 비용 2 → n-1개 선택 완료(종료) | 4 |
| 4 | (1-2) 비용 5 → 사이클 발생, 선택 X | |
| 5 | (2-3) 비용 8 |
풀이 코드 (JAVA)
import java.util.*;
class Solution {
public void union(int[] parent, int x, int y) {
x = find(parent, x);
y = find(parent, y);
if (x < y) {
parent[y] = x;
} else {
parent[x] = y;
}
}
public int find(int[] parent, int x) {
if (parent[x] == x) {
return x;
} else {
return find(parent, parent[x]);
}
}
public int solution(int n, int[][] costs) {
int answer = 0;
Arrays.sort(costs, (o1, o2) -> o1[2] - o2[2]);
// 부모노드 초기화
int[] parent = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
}
// 크루스칼 알고리즘
for (int i = 0; i < costs.length; i++) {
// 부모가 같지 않으면. 즉, 사이클이 생기지 않으면 간선 선택
if (find(parent, costs[i][0]) != find(parent, costs[i][1])) {
answer += costs[i][2];
union(parent, costs[i][0], costs[i][1]);
}
}
return answer;
}
}✅ 코드 설명
find(): 특정 노드의 부모(루트 노드)를 찾는 함수union(): 두 노드를 같은 집합으로 합치는 함수- costs 배열을 가중치 기준으로 정렬하고, 가중치가 작은 간선부터 추가
- 사이클이 발생하는지 체크 후, MST에 포함 여부 결정
