#Disjoint Set ( Union Find ) 알고리즘
▶ 여러개의 노드 중 2개를 선택했을 때 같은 그래프에 있는가를 판별
배열로 나타내면 현재 자기자신을 참조하는 중이다.
1과 2를 연결한다 = Union
노드가 작은 쪽을 참조하도록 한다. 2->1
3과 2를 연결한다 = Union
노드가 작은 쪽을 참조하도록 한다 3->2
이렇게 되면 자연스레 3->2 이고 2->1 이므로 3->2->1 이 된다.
Union
Disjoinset 알고리즘에는 Union이라는 연산이 있다.
어디로 Union(합침) 되느냐는
1. Union-by-Rank : 부모노드의 값에 따라
2. Union-by-Height : 그래프의 깊이에 따라
void union(int x,int y)
{
x = find(x);
y = find(y);
if(a<b) parent[y] = x;
else parent[x] = y;
}노드크기가 작은 것에 합쳐지게(참조하도록) 만드는게 Union연산이다.
사용할 때는 union(find(x),find(x)-1) 을 통해 사용한다.
Find
find 연산은 각 노드가 속한 그래프의 대표값(대표노드)를 뱉어내는데
만약 find 연산으로 값이 같다면 같은 그래프에 속하고 있다는 걸 알 수 있다.
int find(int x)
{
if(x==parent[x]) return x;
return parent[x] = find(parent[x]);
}
만약 6이 1을 참조하려면 6->5->2->1 3번을 거쳐가야 한다.
return parent[x] = find(parent[x]);
이 연산을 사용하면 각 노드가 바로 루트 노드를 참조하도록 할 수 있다.
이것을 경로 압축 이라 하고 시간복잡도는 O(N) 이다.
간단한 알고리즘 이지만, 문제에 있어서 어떻게 적용시켜야 할 지 고민해봐야겠다.
ㅎㅅㅇ