Jungol[1863] - 종교

링크

JUNGOL | 종교 > 문제은행

문제설명

• DisjointSet 개수 구하기

문제풀이

• DisjointSet 개수 구하기

문제코드

import java.util.Scanner;

public class Main1863_종교 {

    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)];
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int m = sc.nextInt();

//        tree node 생성
        parent = new int[n+1];
        for (int i = 1; i <= n; i++) {
            makeSet(i);
        }

//        Union
        for (int i = 0; i < m; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
//            union_normal(a, b);
//            union_by_height(a, b);
            union_by_weight(a, b);
        }

//        Find Root
        int ans = 0;
        for (int i = 1; i <= n; i++) {
            if(parent[i]<0) ans++;
        }

        System.out.println(ans);
    }
}

잘한 점

• DisjointSet 공부하였음

효율성

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

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

결론

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