[ 개념 ] 32. Graph - 유니온 파인드(Union-Find) 알고리즘

> 유니온 파인드(Union-Find)

---

그래프 알고리즘으로 합집합 찾기 알고리즘이다.

상호 배타적 집합(Disjoint-set)이라고도 한다.

Disjoint Set이란 서로 중복되지 않는 부분집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료구조이다.

유니온파인드의 특징

Union-Find란 Disjoint Set을 표현할 때 사용하는 알고리즘이다.

• 집합을 구현하는 데는 비트 벡터, 배열, 연결 리스트를 이용할 수 있으나 그중 가장 효율적인 트리 구조를 이용하요 구현한다.
• make-set(x)
  • 초기화
  • x를 유일한 원소로 하는 새로운 집합을 만든다.
• union(x,y)
  • 합하기
  • x가 속한 집합과 y가 속한 집합을 합친다.
• find(x)
  • 찾기
  • x가 속한 집합의 대표값(루트 노드값)을 반환한다. 즉 x가 어떤 집합에 속해 있는지 찾는 연산

여러 노드가 존재 할 때 두 개의 노드를 선택해서, 현재 두 노드가 서로 같은 그래프에 속하는지 판별하는 알고리즘이다.

총 2가지의 연산으로 이루어져 있다.

• Find : x가 어떤 집합에 포함되어 있는지 찾는 연산
• Union : x와 y가 포함되어 있는 집합을 합치는 연산

유니온 파인드의 동작방식

위와 같이 모두 연결되지 않고 각자 자기 자신만을 집합의 원소로 가지고 있을 때, 모든 값이 자기 자신을 가리키도록 만든다.

i : 노드번호, P[i]: 부모 노드 번호를 의미하며, 즉 자기 자신이 어떤 부모에 포함되어 있는지를 의미한다.

정리하면 Parent[i] = i

Union(1,2), Union(3,4)를 해주어 위와 같이 노드를 연결해준다.

위와 같이 표로 표현이 된다. 2번째 인덱스에 '1'이 들어가고, 4번인덱스에 '3'이 들어간다.

이와 같이 부모를 합칠 때는 일반적으로 더 작은 값 쪽으로 합친다. 이것을 합칩(Union) 과정이라고 한다.

)

1,2,3이 연결될 때는 위와 같은 표로 표현이 된다.

1과 3은 부모가 다르기 때문에 1과 3이 연결되었는지 파악하기 힘들다. 따라서 재귀함수가 사용된다.

3인 부모인 2를 먼저 찾고, 2인 부모인 1을 찾아 결과적으로 3의 부모는 1이되는 것을 파악하는 것이다.

Union의 과정이 수행된 후에는 다음과 같은 표로 바뀌게 된다.

결국 1,2,3의 부모는 모두 1이기 때문에 이 세가지 노드는 모두 같은 그래프에 속한다는 것을 알 수 있다.

해당 경로를 바꿔주는 과정은 아래와 같은 그림으로 변하게 된다.

유니온파인드의 최적화

-최악의 상황

• 트리구조가 완전 비대칭인 경우
• 연결 리스트 형태
• 트리의 높이가 최대가 된다
• 원소의 개수가 N일 때, 트리의 높이가 N-1이므로 union과 find(x)의 시간 복잡도가 모두 O(N)이 된다.
• 배열로 구현하는 것 보다 비효율적이다.

- find 연산 최적화

• 경로 압축(Path Compression)
• 시간 복잡도 : O(logN)

// 초기화
int root[MAX_SIZE];
for(int i=0; i<MAX_SIZE; i++){
    root[i]= i;
}

// find(x) : 재귀 이용
int find(int x){
    if(root[x] == x)
        return x;
    else P
        // 경로 압축
        // find하면서 만난 모든 값의 부모 노드를 root로 만든다.
        return root[x] = find(root[x]);
}

- union 연산 최적화

• union-by-rank(union-by-height)
• rank에 트리의 높이를 저장한다.
• 항상 높이가 더 낮은 트리를 높은 트리 밑에 넣는다.

//초기화
int root[MAX_SIZE];
int rank[MAX_SIZE];    // 트리의 높이를 저장할 배열
for(int i=0; i<MAX_SIZE; i++){
    root[i] = i;
    rank[i] = 0;    // 트리의 높이 초기화
}

// find(x): 재귀이용
int find(int x){
    // 위와 동일
}

// union1(x, y) : union-by-rank 최적화
void union(int x, int y){
    int x = find(x);
    int y = find(y);

    // 두 값의 root가 같으면(이미 같은 트리) 합치지 않는다.
    if(x == y)
        return;

    // "union-by-rank 최적화"
    // 항상 높이가 더 낮은 트리를 높이가 높은 트리 밑에 넣는다. 즉 높이가 더 높은 쪽을 rank로 삼음
    if(rank[x] < rank[y]){
        root[x] = y;    // x의 root를 y로 변경
    } else {
        root[y] = x;    // y의 root를 x로 변경

        if(rank[x] == rank[y])
            rank[x] ++;    // 만약 높이가 같다면 합친 후 (x의 높이 + 1)
    }
}

두 원소가 속한 트리의 전체 노드의 수를 구하는 경우

// union2(x, y): 두원소가 속한 트리의 전체 노드의 수 구하기
int nodeCount[MAX_SIZE];
for(int i=0; i<MAX_SIZE; i++){
    nodeCount[i] = i;
}

int union2(int x, int y) {
    int x = find(x);
    int y = find(y);

    // 두 값의 root가 같지 않으면
    if(x != y){
        root[y] = x;    // y의 root를 x로 변경
        nodeCount[x] += nodeCount[y];    // x의 node 수에 y의 node 수를 더한다.
        nodeCount[y] = 1;    // x에 붙은 y의 node 수는 1로 초기화
    }
    return nodeCount[x];    // 가장 root의 node 수 반환
}

코드

public class UnionFind{
    public static int[] parent = new int[1000001];

    public static int find(int x){
        if(x == parent[x])
            return x;
        else
            return parent[x] = find(parent[x]);
    }

    public static void union(int x, int y){
        int x = find(x);
        int y = find(y);
        //같은 부모를 가지고 있지 않을 때
        if(x != y){
            //y가 x보다 크다는 것을 가정하면
            parent[y] = x;
            // 더 작은 값으로 넣어 줄 때 다음과 같이 표현
            /*
            if(x < y) parent[y] = x;
            else parent[x] = y;
            */
        }
    }

    //같은 부모 노드를 가지는지 확인
    public static boolean isSameParent(int x, int y){
        x = find(x);
        y = find(y);
        if(x == y)
            return true;
        else
            return false;
    }

    public static void main(String[] args){
        for(int i=1; i<=8; i++){
            parent[i] = i;
        }
        union(1,2);
        union(2,3);
        System.out.println("1과 3은 연결되어 있나요? -> "+isSameParent(1,3));
    }
}

유니온파인드 관련된 예시

1. 전체 집합이 있을 때 구성원소들이 겹치지 않도록 분할하는 데 자주 사용된다.

   • Kruskal MST 알고리즘에서 새로 추가할 간선의 양끝 정점이 같은 집합에 속해 있는지(사이클 형성 여부 확인)에 대해 검사하는 경우

   • 초기에 {0}, {1}, {2}, ... {n}이 각각 n+1개의 집합을 이루고 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하는 경우

     집합의 표현 - 백준 1717번

   • 어떤 사이트의 친구 관계가 생긴 순서대로 주어졌을 때, 가입한 두 사람의 친구 네트워크에 몇 명이 있는지 구하는 프로그램을 작성하는 경우

     친구 네트워크 - 백준 4195번

그외

바이러스 - 백준 2606번

섬 연결하기 - 프로그래머스 42861번

참고

https://brenden.tistory.com/33