서로소 집합이란?
수학에서 서로소 집합(Disjoint Sets)이란 공통 원소가 없는 두 집합을 의미한다.
예를 들어 집합 {1, 2}와 집합 {3, 4}는 서로소 관계이다. 반면에 집합 {1, 2}와 {2, 3}은 2라는 원소가 두 집합에 공통적으로 포함되어 있기 때문에 서로소 관계가 아니다.
서로소 집합 자료구조
- 서로소 집합 자료구조란 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조
- union / find 연산으로 조작할 수 있다.
- union 연산은 2개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산이다.
- find 연산은 특정한 원소가 속한 집합이 어떤 집합인지 알려주는 연산이다.
- 서로소 집합 자료구조는 union-find 자료구조라고 불리기도 한다.
- 두 집합이 서로소 관계인지를 확인할 수 있다는 말은 각 집합이 어떤 원소를 공통으로 가지고 있는지를 확인할 수 있다는 말과 같기 때문이다.
- 서로소 자료구조를 구현할 때는 트리 자료구조를 이용하여 집합을 표현한다.
서로소 집합 알고리즘
서로소 집합 정보(합집합 연산)가 주어졌을 때 트리 자료구조를 이용해서 집합을 표현하는 서로소 집합 계산 알고리즘은 다음과 같다.
- union(합집합) 연산을 확인하며, 서로 연결된 두 노드 A, B를 확인한다.
- A와 B의 루트 노드 A’, B’를 각각 찾는다.
- A’를 B’의 부모노드로 설정한다. (B’가 A’를 가리키도록 한다. → 더 큰 루트 노드가 더 작은 루트 노드를 가리키도록 한다.)
- 모든 union(합집합) 연산을 처리할 때까지 1번 과정을 반복한다.
동작 과정
[초기 단계] 노드의 개수 크기의 부모 테이블을 초기화한다.
부모 테이블은 말 그대로 부모에 대한 정보만을 담고 있다. 다시 말해 특정한 노드의 부모에 대해서만 저장하고 있다. 우리가 실제로 루트를 확인하고자 할 때는 재귀적으로 부모를 거슬러 올라가서 최종적인 루트 노드를 찾아야 한다.
[Step 1] Union(1,4)
노드 1과 노드 4의 루트 노드를 각각 찾는다. 현재 루트 노드는 각각 1과 4이므로 더 큰 번호에 해당하는 루트 노드 4의 부모를 1로 설정한다.
[Step 2] Union(2,3)
노드 2와 노드 3의 루트 노드를 각각 찾는다. 현재 루트 노드는 각각 2와 3이므로 더 큰 번호에 해당하는 루트 노드 3의 부모를 2로 설정한다.
[Step 3] Union(2,4)
노드 2와 노드4의 루트 노드를 각각 찾는다. 현재 루트 노드는 각각 2와 1이므로 더 큰 번호에 해당하는 루트 노드 2의 부모를 1로 설정한다.
[Step 4] Union(5,6)
노드 5와 노드 6의 루트 노드를 각각 찾는다. 현재 루트 노드는 각각 5와 6이므로 더 큰 번호에 해당하는 루트 노드 6의 부모를 5로 설정한다.
[최종]
코드
private var v: Int = 0 // 노드의 개수
private var e: Int = 0 // 간선의 개수(Union 연산)
private val parent = IntArray(100001) // 부모 테이블
// 특정 원소가 속한 집합 찾기
private fun findParent(x: Int): Int {
// 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출
if (x == parent[x]) return x
return findParent(parent[x])
}
private fun unionParent(a: Int, b: Int) {
val xa = findParent(a)
val xb = findParent(b)
if (xa < xb) parent[xb] = xa
else parent[xa] = xb
}
fun main() {
val sc = Scanner(System.`in`)
v = sc.nextInt()
e = sc.nextInt()
// 부모 테이블상에서, 부모를 자기 자신으로 초기화
for (i in 1 .. v) {
parent[i] = i
}
// Union 연산을 각각 수행
for (i in 0 until e) {
val a = sc.nextInt()
val b = sc.nextInt()
unionParent(a, b)
}
// 각 원소가 속한 집합 출력하기
print("각 원소가 속한 집합: ")
for (i in 1 .. v) {
print("${findParent(i)} ")
}
println()
// 부모 테이블 내용 출력하기
print("부모 테이블: ")
for (i in 1 .. v) {
print("${parent[i]} ")
}
println()
}비효율적인 find 함수 개선
- 위 알고리즘의 find 함수는 비효율적인 점이 존재한다. 최악의 경우 find 함수가 모든 노드를 확인하는 터라 시간 복잡도가 O(V)라는 점이다.
- 노드의 개수가 V개일 때 find 혹은 union 연산의 개수가 M개라면 전체 시간 복잡도는 O(VM)이 되어 비효율적이다.
- 경로 압축(Path Compression) 기법을 적용해 시간 복잡도를 개선할 수 있다.
- find 함수를 재귀적으로 호출한 뒤에 부모 테이블 값을 갱신하는 기법이다.
- 경로 압축 기법을 적용하게 되면 find 함수를 호출한 이후에, 해당 노드의 루트 노드가 바로 부모 노드가 된다.
[기존 방법]
// 특정 원소가 속한 집합 찾기
private fun findParent(x: Int): Int {
// 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출
if (x == parent[x]) return x
return findParent(parent[x])
}[경로 압축]
private fun findParentPathCompression(x: Int): Int {
if (x == parent[x]) return x
return findParent(parent[x]).also { parent[x] = it }
}서로소 집합 알고리즘의 시간 복잡도
- 노드의 개수가 V개이고, 최대 V-1개의 union 연산과 M개의 find 연산이 가능할 때 경로 압축 기법을 이용한 알고리즘의 시간 복잡도는 O(V+M(1+log2-m/vV)라는 것이 알려져 있다.
- 예를 들어 노드의 개수가 1,000개이고 union 및 find 연산이 총 100만번 수행된다고 가정할 때 대략 V + Mlog2V를 계산해서 약 1,000만번 가량의 연산이 필요하다
Java & Backend Developer