•
정의
◦
상호 배타적 집합, 서로소 집합이라고도 부른다.
◦
여러 노드가 존재할 때 특정 두 개의 노드를 같은 집합으로 묶고 어떤 두 노드가 같은 집합에 있는지 확인하는 알고리즘이다.
•
구현
◦
유니온 파인드 알고리즘은 Union, Find 두 연산을 수행한다.
▪
Union 연산은 서로 다른 두 개의 집합을 하나의 집합으로 병합하는 연산을 수행한다. 이는 합집합 연산과 같다.
public void union(int a, int b){
int fa = find(a); // a의 부모를 찾는다.
int fb = find(b); // b의 부모를 찾는다.
if (fa != fb) {
unf[fa] = fb; // b의 부모가 더 작을 것이므로 a의 부모의 값을 b의 부모의 값으로 바꿔준다.
}
}
C#
복사
•
a가 3일 때, 부모 배열이 다음과 같다면? 1, 1, 2, 4, 5, 6, 7
◦
a는 2로 간다. 2는 자기 자신과 값이 같지 않으므로 자신의 부모인 1로 보낸다.
◦
이 과정에서 경로 압축을 사용하면 자신의 루트 노드를 곧바로 접근할 수 있게 된다.
▪
Find 연산은 하나의 원소가 어떤 집합에 속해있는지 확인한다.
public int find(int v){
if (v == unf[v]) {
return v;
}
return unf[v] = Find(unf[v]); // 경로 단축을 사용한 모습이다.
}
C#
복사
◦
n개의 노드에 대해서 유니온 파인드를 진행할 경우, 길이가 n인 부모 배열이 필요하다.
▪
초기의 부모 배열은 인덱스와 같은 값을 가지고 있다.
