디스조인트 세트(Disjoint Set) 자료 구조는 서로소 집합이라고도 불리며, 서로 중복되지 않는 부분 집합들로 이루어진 원소들에 대한 정보를 효율적으로 표현하는 자료 구조입니다. 이 자료 구조는 여러 그래프 알고리즘과 크루스칼 알고리즘 같은 최소 비용 신장 트리(Minimum Spanning Tree) 알고리즘에 널리 사용되며, 이외에도 연결 요소 확인, 동치 클래스 등 여러 분야에서 사용됩니다.
디스조인트 세트 자료 구조의 기본 개념
디스조인트 세트 자료 구조는 집합들을 나타내는 데이터 구조입니다. 각 집합은 대표 원소를 갖고 있으며, 같은 집합에 속하는 모든 원소들은 같은 대표 원소를 갖습니다. 디스조인트 세트는 다음과 같은 두가지 기본 연산을 지원합니다.
- 합집합(Union): 두 집합을 하나의 집합으로 합칩니다.
- 찾기(Find): 특정 원소가 속한 집합의 대표 원소를 찾습니다.
디스조인트 세트 자료 구조는 일반적으로 배열이나 트리를 이용하여 구현됩니다.
크루스칼 알고리즘에서 디스조인트 세트 자료 구조 활용하기
크루스칼 알고리즘은 최소 비용 신장 트리를 구하는 데 사용되는 알고리즘으로, 그래프에서 사이클을 형성하지 않으면서 모든 정점을 연결하는 간선의 부분 집합을 찾습니다. 이때 간선들은 가중치를 가지고 있으며, 최소 비용 신장 트리는 가중치의 합이 최소인 트리입니다.
크루스칼 알고리즘에서는 간선들의 가중치를 기준으로 오름차순으로 정렬한 후, 가장 작은 가중치를 가지는 간선부터 시작하여 사이클을 형성하지 않는 간선들을 순서대로 선택합니다. 이때, 디스조인트 세트를 사용하여 각 정점이 어떤 집합에 속하는지를 유지하면서 사이클 유무를 확인할 수 있습니다.
class DisjointSet(private val size: Int) {
private val parent = IntArray(size)
private val rank = IntArray(size)
init {
for (i in 0 until size) {
parent[i] = i
rank[i] = 0
}
}
fun find(x: Int): Int {
if (parent[x] != x) {
parent[x] = find(parent[x])
}
return parent[x]
}
fun union(x: Int, y: Int) {
val rootX = find(x)
val rootY = find(y)
if (rootX == rootY) {
return
}
if (rank[rootX] > rank[rootY]) {
parent[rootY] = rootX
} else {
parent[rootX] = rootY
if (rank[rootX] == rank[rootY]) {
rank[rootY]++
}
}
}
}
위 코드는 크루스칼 알고리즘에서 사용될 수 있는 간단한 디스조인트 세트의 구현 예시입니다. find 함수는 해당 원소가 속한 집합의 대표 원소를 찾는 함수이고, union 함수는 두 집합을 합치는 함수입니다.
마치며
디스조인트 세트 자료 구조는 다양한 분야에서 유용하게 활용될 수 있습니다. 특히 그래프와 집합 관련 문제를 해결하는 데 도움이 되며, 크루스칼 알고리즘과 같은 알고리즘에서 주요한 역할을 합니다. 알고리즘 및 자료 구조를 공부하는데 있어 디스조인트 세트는 중요한 개념이므로, 심층적으로 학습하고 활용하는 것이 유용할 것입니다.
참고 문헌
- Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.