Disjoint Set(Union Find)

참고 : Union Find (Disjoint Set).pdf

개념

• 상호 배타적 집합(서로소 집합, Disjoint Set)만을 대상으로 한다. 따라서 교집합은 없다.
• 상호 배타적 집합을 찾아 합친다.

자료구조

LinkedList

• 같은 집합의 원소들은 하나의 연결 리스트로 관리한다

• 연결 리스트의 맨 앞의 원소를 집합의 대표 원소로 삼는다

• x.parent = x의 상위 노드

 

Linked List representation of Disjoint Set Data Structures - GeeksforGeeks

Tree

• 같은 집합의 원소들은 하나의 트리로 관리한다

• 자식 노드가 부모 노드를 가리킨다

• 트리의 루트를 집합의 대표 원소로 삼는다

• Array를 이용하여 구현

• parent[x] = x의 상위 노드

연산

Make(x)

• 원소 x로만 이루어진 집합을 만든다.

Find(x)

• 원소 x를 포함하는 집합을 알아낸다.

Union(x, y)

• 원소 x를 포함하는 집합과 원소 y를 포함하는 집합을 합한다.

효율성

경로 압축

• Find(x) 탐색과정에서 거치는 노드들이 모두 부모를 가리키도록 하여 노드들의 탐색 depth를 줄여준다.

랭크를 이용한 Union

• 1->2->3->…->N 이런 식으로 편향된 Union이 만들어지면 Find연산을 할 경우 거쳐야 할 노드의 수가 비효율적으로 증가한다.
• 랭크 = Weight
  • 집합이 가지고 있는 원소들의 개수를 랭크로 지정한다.
• 랭크 = Depth
  • 집합이 가지고 있는 최대 depth(height)를 랭크로 지정한다.

효율성 검증

 

Jungol[1863] - 종교

효율성

• 경로 압축 유무
• Union 할 경우 Rank(Height or Weight)를 기준으로 Union 하는 것 유무

경로압축	Union 방식	메모리(MB)	시간(ms)
X	X	stack overflow	-
O	X	83	1295
X	Weight	83	1213
O	Weight	83	1198
X	Height	82	1241
O	Height	84	1227

 

Baekjoon[14868] - 문명

효율성

• Disjoint Set 에서 Find탐색의 효율성을 높이는 방법
  • Rank 기준 Union
  • 경로압축
  • 하나도 안 썼을 경우 시간초과가 난다.
• LinkedList = new LinkedList 기준으로 탐색했을 경우

경로압축	Union방식	메모리(kb)	시간(ms)
X	X	-	시간초과
X	Weight	340968	2116
X	Height	341428	2304
O	X	341028	2212
O	Weight	342592	2184
O	Height	343068	2160

결론

• 경로 압축의 유무, Union 방식 둘 다 효율성에 영향을 크게 미친다.
  • 둘 중에 하나만 적용해도 충분하다.
  • 둘 다 안쓰면 차이가 큼. 시간초과걸릴 위험 큼.
• Union방식에 있어서 Weight, Height 기준의 효율성 차이는 별로 없다.
• 호텔 방 배정 같은 문제는 경로 압축만 이용해도 풀린 이유가 있다.
• 둘 다 중요함

코드

    public static int[] parent;

    /** 음수면 root이면서 rank수 이므로 -1로 초기화 */
    public static void makeSet(int v) {
//        자기 자신을 가르킴
        parent[v] = -1;
    }

    /** 포함된 집합의 root를 찾는다. */
    public static int findSet(int v) {
//      root인 경우
        if (parent[v] < 0) {
            return v;
        }
//        경로압축 - find하는 과정에서 거치는 노드들을 모두 parent[v]를 향하도록 만들어준다.
        else {
            parent[v] = findSet(parent[v]);
        }
//        경로 압축이 끝난 후, 부모반환
        return parent[v];
    }

    /** 두 트리를 결합한다. */
    public static void union_normal(int v1, int v2) {
//        v1 <- v2 병합
//        root = parent
        int root1 = findSet(v1);
        int root2 = findSet(v2);

//      두 원소를 포함한 집합이 같은 집합인 경우
        if (root1 == root2) {
            return;
        }

//        v1 <- v2 병합
        parent[root2] = root1;
    }

    /** 두 트리를 결합한다. */
//    집합에 포함된 노드의 개수를 rank로 두고 union하는 경우
    public static void union_by_weight(int v1, int v2) {
//        root = parent
        int root1 = findSet(v1);
        int root2 = findSet(v2);
//        rank = depth
        int rank1 = parent[root1];
        int rank2 = parent[root2];

//      두 원소를 포함한 집합이 같은 집합인 경우
        if (root1 == root2) {
            return;
        }

//        rank : 둘다 음수임, rank가 깊은 녀석에게 병합
//        rank v1 이 더 깊음 : v1 <- v2 병합
//        같은 경우는 둘 중 아무나 병합해도 상관없음 : v1 <- v2 병합
        if (rank1 <= rank2) {
            parent[root1] += parent[root2];
            parent[root2] = root1;
        }
//        rank v2 이 더 깊음 : v2<-v1 병합
        else if(rank1 > rank2){
            parent[root2] += parent[root1];
            parent[root1] = root2;
        }
    }

    /** 두 트리를 결합한다. */
//    집합의 height(최대 노드 depth)를 rank로 두고 union하는 경우
    public static void union_by_height(int v1, int v2) {
//        root = parent
        int root1 = findSet(v1);
        int root2 = findSet(v2);
//        rank = depth
        int rank1 = parent[root1];
        int rank2 = parent[root2];

//      두 원소를 포함한 집합이 같은 집합인 경우
        if (root1 == root2) {
            return;
        }

//        rank : 둘다 음수임, rank가 깊은 녀석에게 병합
//        rank v1 이 더 깊음 : v1 < -v2 병합
        if (rank1 < rank2) {
//            parent[root1] 의 height는 그대로 유지
            parent[root2] = root1;
        }
//        rank v2 이 더 깊음 : v2<-v1 병합
        else if(rank1 > rank2){
//            parent[root2] 의 height는 그대로 유지
            parent[root1] = root2;
        }
//        같은 경우는 둘 중 아무나 병합해도 상관없음 : v1 <- v2 병합
//        대신 병합되는쪽의 rank가 하나 증가함.
        else if(rank1 == rank2) {
//            parent[root1] 의 height는 하나 증가
            parent[root1] -= 1;
            parent[root2] = root1;
        }
    }

    public static int getRank(int v) {
        return -parent[findSet(v)];
    }