Union-Find 개념

서로소 집합

서로소 집합이란 집합들이 서로 분리관계에 있는 집합

1) 교집합이 없고 한 개의 원소는 1개의 집합에만 포함

2) union-find를 통해서 서로소 집합을 효과적으로 표현 가능

 

집합의 표현

1) 변형된 tree 형식으로 표현

2) 서로소 집합은 부모에 대한 링크만을 가지고 있다.

 

Union

부모가 자기 자신인 원소끼리 연결하여는 것.

즉, 두 서로소 집합을 합하는 것

 

Union 최적화

두 서로소 집합을 합할 때 깊이가 좀 더 얕은 집합을 다른 집합에 추가하는 것

e.g. 깊이가 2인 집합 A, 깊이가 3인 집합 B가 있을 때

1) A에 B를 이어 붙이게 되면 깊이가 4인 A' 집합이 된다.

2) B에 A를 이어 붙이게 되면 깊이가 3인 B' 집합이 된다.

각 집합의 깊이를 저장하고 깊이가 얕은 집합을 다른 집합에 추가

 

Find

하나의 원소가 어떤 집합에 들어있는지 찾는 것

특정 원소의 부모가 자기 자신인 원소가 나타날 때까지 찾는다.

 

Find 최적화

깊이가 깊어지면 root 원소를 찾는데 오래 걸린다.

find 연산에서의 깊이 정보는 의미가 없기 때문에 최대한 모든 노드를 root 바로 아래에 둔다.

 

Union-Find 기본 코드

class UF{
    public int parents[], ranks[], N; //N의 크기가 정해져 있다면 array, N의 크기가 유동적이라면 arrayList 사용
    //public List<Integer> parentsList, ranksList;
    private void init() {
        parents = new int[N];
        ranks = new int[N];
        for(int i = 0; i<N; i++) {
            parents[i] = i; //본인을 부모로 지정
        }
    }
    private int find(int x) {
        if(parents[x] == x) {
            return x;
        }
        return parents[x] = find(parents[x]); // find 최적화, 모두 최상위 root를 부모로 지정하도록
    }
    private int union(int x, int y) {
        int xParent = find(x);
        int yParent = find(y); //두 원소의 부모를 찾는다
        if(xParent == yParent) { //두 원소의 부모가 같다면 이미 합쳐져 있는 상태이므로 아무것이나 둘중 아무 것이나 반환
            return xParent;
        }

        if(ranks[xParent] < ranks[yParent]) { // union 최적화, 부모의 깊이가 더 얕은 집단을 더 깊은 집단에 연결하여 깊이가 커지지 않도록 함
            return parents[xParent] = yParent;
        } else {
            if(ranks[xParent] == ranks[yParent]) { //깊이가 같다면 한쪽의 깊이를 더 깊게 만들어 합친다
                ranks[xParent]++;
            }
            return parents[yParent] = xParent;
        }
    }
}