분리 집합 / 유니온 파인드
분리 집합이란?
- 각 정점을 그룹화시켜서 관리할 때 사용되는 자료구조 + 알고리즘 - 그룹화한다는 것은, 문제 조건에 의해 관계를 만드는 경우이기도 하고, subproblem을 푼 이후 중복연산을 하지 않도록 관계를 기록하는 경우로도 사용 가능하다
분리 집합은 각 정점이 같은 그룹에 속해있는지 아닌지 관리할 수 있는 방법들 중 하나이다. 흔히 아래와 같은 상황일 때 유용하게 쓰이는 만큼, 가장 먼저 고려해야하는 경우도 있다.
즉, A와 C가 직접적인 관계가 없어도 B를 통해 연결이 되는 경우, A와 C 또한 관계가 있다고 보는 경우, 분리 집합이 유용하게 쓰일 수 있다. 서로 관계가 있는 정점들을 하나의 그룹으로 묶는다면, 여러개의 그룹들을 엮는 것처럼 보이기도 한다. 네트워크에서 NAT 구조를 생각해보면 얼추 비슷하다고 생각할 수도 있다. 그룹끼리 연결되면 합쳐져 하나의 그룹이 되기도 한다.
구현 방법
분리 집합은 2개의 단계로 분리된다. Union 단계와 Find 단계. 둘을 합쳐서 유니온-파인드 라고도 부르기도 한다. union은 서로 다른 두 그룹을 하나의 그룹으로 묶는 것, find 단계는 현재 내가 속해있는 그룹이 무엇인지를 찾는 것이라고 생각하면 된다.
구현 방법으로는, 각 정점마다 parent 변수를 두는 것이다. 정점들을 그래프 상에 둔다고 생각해보면, 하나의 그룹은 임의의 centroid가 있고 나머지가 직간접적으로 centroid에 연결되어있는 형태가 될 것이다. 그리고 그 모양은, centroid를 root로 보면 하나의 트리처럼 보인다. 유니온파인드에서는, 그룹이 트리 모양처럼 보인다는 발상에서 착안되었다.
parent 변수는 단어의 의미처럼, 현재 노드의 부모 노드를 기록한다. 부모가 없다면 본인이 부모, 즉 centroid라고 생각하자. 초기 상태에는 모든 parent 변수가 자기 자신을 가리킬 것이다. find 함수는 본인이 어떤 그룹에 속해있는지 확인하는 함수이다. 즉, 본인이 속한 그룹의 centroid를 반환해주면 된다. 그룹마다 centroid는 하나기 때문이다. 그럼 현재 위치에서 centroid를 어떻게 찾을 수 있을까? 현재 위치가 그룹 내의 트리에서 하나의 노드이므로, parent를 계속해서 거슬러 올라가다보면 root를 찾을 수 있을 것이다. 그리고 그것이 centroid인 것은 이미 얘기가 되었다. 이것을 구현해보자
1
2
3
4
5
6
7
int find(int x) {
if (parent[x] == x) {
return x;
} else {
return find(parent[x]);
}
}
계속해서 재귀적으로 parent를 올라가서 최종적으로 root인 부분에서 그 index를 반환해주면 된다. 그런데, 이렇게 하면 x의 depth가 클수록 계속해서 재귀를 반복해야하는 상황이 생긴다. find 함수는 어떤 상황에서든지 root를 반환하게 하면 depth를 반복하는 것은 없앨 수 있다. 그래서, parent 변수를 직접 수정하자. parent를 부모를 저장하는게 아니라 계산된 root를 저장하는 것이다! 이렇게 하면 다음에 x에 대해 find를 다시 호출하면 parent에 이미 root가 저장되어있으므로 depth를 모두 계산할 필요 없이 바로 root로 직행이 가능하다!
1
2
3
4
5
6
7
int find(int x) {
if (parent[x] == x) {
return x;
} else {
return parent[x] = find(parent[x]);
}
}
union 함수는 두개의 그룹을 합치는 것이다. 그룹 내의 모든 점에 대해서 parent를 지정해주어야하나 생각할 수도 있지만, 사실 그렇게까지는 필요 없다. 두 그룹의 root를 찾은 다음, 하나의 그룹의 root를 다른 root의 자식 노드로 연결시켜주기만 하면, 트리 구조를 깨지 않으면서 서로 연결이 되므로, 하나의 그룹으로 연결할 수 있게 된다.
1
2
3
4
5
6
7
void union(int a, int b) {
int x = find(a), y = find(b);
if (x != y) {
parent[y] = parent[b] = x;
}
return;
}