Union Find Disjoint Set (UFDS)

유니온 파인드 상호배타적 집합

 

  상호 베타적인 집합들을 모델랑하는 자료구조이다. 여기서 상호베타적이라는 말은 임의의 두 집합의 교집합이 공집합이라는 뜻이고 이는 각집합이 서로 서로소임과 동치이다.

  이 자료구조를 이용하면 어떤 원소가 어느 집합에 속해 있는지를 판별하는 작업, 혹은 두 원소가 동일한 집합에 속하는지 판별하는 작업, 그리고 상호 베타적인 두 집합을 더 큰 하나의 집합으로 합치는 작업을 거의 O(1)이라는 시간 복잡도에서 해낼 수 있다.

  이를 이용하여 해결할 수 있는 대표적인 문제로는 무방향 그래프의 연결된 컴포넌트를 찾는 문제를 풀 수 있다. 각 그래프의 정점을 별개의 상호 베타적 집합으로 초기화 하고, 두 정점을 잊는 간선을 탐색하며 두정점이 속한 집합을 하나의 집합으로 합친다. 이와 같은 알고리즘을 통해 해당 문제를 쉽게 해결할 수 있다. 시간복잡도는 O(E) (E는 간선의 수) 이다.

 

유니온 파인드 구현

 

  유니온 파인드의 각 집합은 트리 구조이다. 각 집합의 대표원소는 트리의 로투가 된다. 유니온 파인드의 전체 구조는 포레스트가 된다. 이러한 구현체를 통해 위에서 설명한 3가지 작업 즉, 어떤원소가 어느 집합에 속해 있는지를 판별하는 작업 등... 을 수행할 수 있다. 어떤원소가 어느 집합에 속해있는지는 해당 원소의 부모를 따라 올라가 해당원소가 속한 트리의 대표원소 즉, 루트를 찾으면 된다. 임의의 두 원소가 같은 집합에 속했는지의 여부를 알기 위해서는 두 원소의 대표원소를 구해 대표원소가 같은지를 확인하면된다. 마지막으로 임의의 두집합을 합치는것은 훨씬 더 간단하다. 두개의 트리중 하나를 한개의 트리 리프에 달아버리면 된다.

  여기서 구현되는 트리는 노드를 클래스나 구조체로 정의하고 이를 포인터로 잇는식으로 구현할 필요가 없다. 루트를 탐색하고 루트를 변경하는 작업만을 수행하기 때문에 배열 두개만을 이용하여 트리를 구현할 수 있다. 사용되는 두개의 배열은 아래와 같다

 

p[i] = i의 부모 노드의 인덱스

randk[i] = i를 루트로 하는 트리 높이의 상한

 

  루트의 부모는 자기 자신이다. 즉, p[root] = root 가 된다. 유니온 파인드 자료구조를 사용함에 있어서 시간복잡도가 가장 높은 작업은 속한 집합을 알아내기 위하여 해당노드의 부모를 따라서 트리의 루트까지 올라가는 작업이다. 이 작업의 효율을 올리기위한 두가지의 휴리스틱이 있다.

  한가지는 '랭크에 의한 합치기 휴리스틱'이다. 이는 두 개의 다른 집합을 하나의 집합으로 합칠경우 높이가 더높은 집합 즉 트리밑에 높이가 더 낮은 집합을 붙인다. 이러한 경우 전체적인 트리의 높이는 더 늘어나지 않게 된다. 반대의 경우 트리의 높이는 커질 수 밖에 없다. 예를들어 트리1과 트리2를 합친다고 가정해보자 트리1의 높이는 1이고 트리2의 높이는 2이다. 트리1 밑에 트리2를 붙일경우 트리1의 루트에 높이가 2인 트리가 붙는다. 트리1의 높이는 1이므로 루트에 높이2자리 트리가 붙으면 자연히 트리1의 높이는 커질 수 밖에없다. 반대의 경우는 당연히 높이가 커질 수 없는것이다. 트리의 높이가 작아야지만 리프로부터 루트까지 거꾸로 올라가는 시간이 짧은것은 지당한 사실이다.

  두번째 휴리스틱은 '경로압축 휴리스틱' 이다. 이 휴리스틱은 루트 탐색작업에 소요되는 시간을 굉장히 효율적으로 줄여준다. 현재 임의의 노드에서 루트를탐색하기 위해서는 노드의 부모를 찾고 그 부모가 루트가 아니면 다시 해당노드 부모의 부모를 찾아 부모가 루트일때까지 이작업을 반복한다. 이때 현재부터 루트까지 올라가는 길목에 있는 모든 노드의 부모를 루트로 변경하는 것이다. 이는 다음번에 위 노드들이 속한 집합의 대표워소를 탐색할때 1번의 연산으로 루트를 찾을 수 있게해준다. 트리의 구조는 변경되지만 이러한 변경이 루트 탐색작업을 더욱 효율적으로 할 수 있게 해줄뿐이다. 바로 이 휴리스틱 때문에 rank배열이 저장하고 있는 값이 트리의 높이가 아니라 트리 높이의 상한이 되는 것이다. 해당 자료 구조의 구현체는 아래와 같다.

 

ADT(Abstract Data Type)

 

int findSet(int i) = i가 속한 집합의 대표원소를 찾는다.

bool isSameSet(int i, int j) = i와 j가 같은 집합에 속했는지의 여부를 반환한다.

void unionSet(int i, int j) = i가 속한 집합과 j가 속한 집합을 합친다.

 

Code of Union Find Disjoint Set

 

class UnionFind{

private:    vi p, rank;    //vi는 vector<int> 이다.

public:

UnionFind(int n) {    rank.assign(n, 0);

p.resize(n);    for(int i = 0; i < n; ++i)    p[i] = i;    }

int findSet(int i) {

return (i == p[i] ? i : (p[i] = findSet(p[i])));    }

bool isSameSet(int i, int j) {    return findSet(i) == findSet(j);    }

void unionSet(int i, int j) {

if(!isSameSet(i, j)) {

int x = findSet(i), y = findSet(j);

if(rank[x] < rank[y])

p[x] = y;

else{

p[y] = x;

if(rank[x] == rank[y])    ++rank[x];

}

}    }    };