Union-Find

Union(X, Y) 연산

    - 서로 중복되지 않는 두 개의 집합을 병합

    - X가 속한 집합(부모)에 Y가 속한 집합(부모)을 병합

Find(X) 연산

    - 하나의 원소가 어떤 집합(부모)에 속해있는지를 반환

    - X가 속한 집합(부모)을 찾아 반환

 

 

 

동작

 

 

 

구현

    - 배열로 구현

        * Union(X, Y) 연산에서 모든 원소를 순회하면서 Y가 속한 집합 번호를 X가 속한 집합 번호로 변경

        * Union(X, Y)의 시간복잡도 O(n)

        * Find(X) 연산에서 한 번에 X가 속한 집합을 찾음

        * Find(X)의 시간 복잡도 O(1)

 

    - 트리로 구현

        * Union(X, Y) 연산에서 X가 속한 집합의 자손으로 Y가 속한 집합을 붙임

        * Union(X, Y)의 시간복잡도 O(logN)

        * Find(X) 연산에서 트리를 내려가면서 탐색

        * Find(X)의 시간 복잡도 O(logN), 최악의 경우는 O(N)

 

    - 트리 구조가 안정적이고 빠르기 때문에 트리로 구현

 

    - 기본적인 Union-Find 알고리즘

int parents[MAX_SIZE];
 
// 부모 노드를 자기 자신으로 초기화
for (int i = 0; i < MAX_SIZE; i++) parents[i] = i;
 
 
int find_parent(int x) {
    // 현재 노드의 부모 노드가 자기 자신이면 반환
    if (parents[x] == x) return x;
    // 부모 노드를 찾을 때까지
    return find_parent(parents[x]);
}
 
 
void union_parents(int a, int b){
    // 각 원소가 속한 트리의 부모 노드를 찾기
    a = find_parent(a);
    a = find_parent(b);
    
    // 큰 값에 부모 값을 저장 즉, 작은 값이 부모 노드가 된다.
    if(a > b) parents[a] = b;
    else parents[b] = a;
}

 

 

    - 최적화 Union-Find 알고리즘

        * 트리로 구현할 경우, 노드가 편향되어 트리의 높이가 N이 되어 시간복잡도 O(N)을 갖음

 

        * Find 연산 최적화 : 경로 압축

            + 시간복잡도 : O(logN)

// 초기화
int parents[MAX_SIZE];
 
for (int i = 0; i < MAX_SIZE; i++) parents[i] = i;
 
 
int find_parent(int x) {
    if (parents[x] == x) return x;
    // 경로 압축
    // find_parent 하면서 만난 모든 값의 부모 노드를 모두 최종 부모 노드로 변경
    return parents[x] = find_parent(parents[x]);
}

 

 

        * Union 연산 최적화 : Union-by-rank

            + rank에 트리의 높이를 저장하여 항상 높이가 더 낮은 트리를 높이 가 높은 트리 밑에 붙임

// 초기화
int parents[MAX_SIZE];
int rank[MAX_SIZE]; // 트리의 높이를 저장할 배열
 
for (int i = 0; i < MAX_SIZE; i++) {
      parents[i] = i;
      rank[i] = 0; // 트리의 높이 초기화
}
 
 
 
void union_parents(int a, int b){
       a = find_parent(a);
      b = find_parent(b);
 
       // 부모가 같으면 병합하지 않음
       if(a == b) return;
 
       // union-by-rank 최적화
       // 항상 높이가 더 낮은 트리를 높이가 높은 트리 밑에 넣는다. 
       // 즉, 높이가 더 높은 쪽을 부모로 삼음
       if(rank[a] < rank[b]) root[a] = b; // x의 root를 y로 변경
    else {
         root[b] = a; // y의 root를 x로 변경
 
         // 만약 높이가 같다면 합친 후 (x의 높이 + 1)
         if(rank[a] == rank[b]) rank[a]++;
       }
}