Union Find

1. Union Find 자료구조 ( 서로소 집합 자료 구조)

 

Union find 자료 구조는 서로소 집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료구조이고, find와 union 연산을 제공한다.

 

 

find 연산

해당 원소가 속한 집합의 대표를 반환한다.

위와 같은 서로소 집합이 주어졌을 때, 대표는 1번과 2번이고 find 연산의 결과는 아래와 같다.

 

find(1) = 1

find(3) = 1

find(4) = 1

find(5) = 1

find(2) = 2

find(6) = 2

 

union 연산

두 개의 집합을 하나의 집합으로 합친다.

 

초기 상태

union (1, 2) 

 

union (3, 4)

union (1, 5)

union (1, 3) 이후 상태

 

 

---

 

2. 구현 방법

자신의 부모를 지시하는 배열을 만들어 find와 union 연산을 구현할 수 있다.

 

parent 배열 생성 및 초기화

static int[] parent = new int[10];
for(int i=0;i<10;i++) {
    parent[i] = i;
}

 

추후 find 연산에서 집합의 대표를 찾을 때 사용하기 위해, 자신을 지시하도록 초기화 한다.

 

 

 

 

 

find 연산

static int find(int a) {
    // a가 root(대표)이면 반환
    if(parent[a] == a)return a;
    // 부모의 대표를 찾도록 재귀 호출
    return find(parent[a]);
}

a의 부모가 a이면,  a가 대표라는 뜻이므로 a를 반환한다.
그렇지 않으면 부모의 대표를 찾도록 재귀 호출 한다.

find(3)

자신을 지시하고 있지 않기 때문에 부모의 대표를 찾는다.
find(parent[3]) == find(1)

find(1)

자기 자신을 지시하고 있으므로 본인을 리턴한다.

결과 :  find(3) = 1

 

 

 

 

 

union 연산

static void union(int a,int b) {
    a = find(a);
    b = find(b);
    if(a==b)return;
    parent[b] = a;
}

a가 속해있는 집합과 b가 속해있는 집합을 합치기 위해,
a 집합의 대표와 b 집합의 대표를 찾은 뒤 같은지 비교를 한다.(같다면 이미 같은 집합)
다르다면 parent[b]가 a 집합의 대표를 지시하도록 한다.

union(5,4)

5가 속해있는 집합의 대표 1을 찾고, 4가 속해있는 집합의 대표 3을 찾는다.

3의 부모를 1로 지시하게 한다.

 

 

3. 최적화

아래와 같은 선형 트리를 가진 union find 자료구조에서는 find 연산의 시간 복잡도가 O(N)이 걸린다.

선형트리가 생기는 것을 방지하여 find 연산의 시간 복잡도를 줄일 수 있는 최적화 방법 소개

• 경로 압축 (Path Compression )
• union by rank

 

경로 압축 (Path Compression)

static int find_PathCompression(int a) {
    if(parent[a] == a)return a;
    return parent[a] = find_PathCompression(parent[a]);
}

find의 결과를 자신의 부모로 갱신한다.
자신의 부모를 대표로 변경하여 한번에 집합의 대표를 찾을 수 있도록 한다.

find(4) 호출

 

 

 

find(4)는 재귀적으로 find(parent[4]) == find(3)을 호출

 

 

 

 

find(3)는 재귀적으로 find(parent[3]) == find(2)을 호출

 

 

 

 

 

find(2)는 재귀적으로 find(parent[2]) == find(1)을 호출

 

 

 

 

 

 

find(1)은 1을 리턴하고,
find(1)을 호출 했던 find(2)는 리턴받은 값(1)을 자신의 부모로 갱신

 

 

 

 

 

 

find(2)은 1을 리턴하고,
find(2)을 호출 했던 find(3)는 리턴받은 값(1)을 자신의 부모로 갱신

 

 

 

 

 

 

 

 

find(3)은 1을 리턴하고,
find(3)을 호출 했던 find(4)는 리턴받은 값(1)을 자신의 부모로 갱신

 

union by rank

union by rank는 union 과정에서 항상 작은 집합을 큰 집합의 밑에 붙이는 방법이다.
여기서 작은 집합은 트리의 높이나 집합의 크기를 기준으로 선택한다.

(집합의 크기를 기준으로 사용 함)

 

1번이 대표인 집합이 크기 때문에 2번이 대표인 집합이 밑에 붙는다.

 

 

 

size 배열 생성 및 초기화

static int[] size = new int[10];
for(int i=0;i<10;i++) {
    size[i] = 1;
}

union by rank를 위해 size를 관리할 배열을 생성하고 1으로 초기화한다.

 

 

 

 

 

 

unionByRank

static void unionByRank(int a,int b) {
    a = find(a);
    b = find(b);
    if(a==b)return;
    if(size[a] > size[b]) {
        size[a] += size[b];
        parent[b] = a;
    }
    else {
        size[b] += size[a];
        parent[a] = b;
    }
}

집합의 사이즈를 비교하여 사이즈가 큰 집합이 부모가 되도록 한다.

 

 

 

 

 

비교

최적화 없는 코드

 

 

PathCompression 최적화 코드

 

 

unionByRank 최적화 코드

 

PathCompression + unionByRank 최적화 코드

 

 

PathCompression을 쓰던 unionByRank를 쓰던 상관 없지만
구현이 간단한 Path Compression을 쓰는게 좋을 듯..?
( 집합을 합치기 전으로 돌리기 위해 의도적으로 PathCompression을 하지 않는 경우도 있다고 하는데 코테 수준은 아닌거 같아요..)

위 기법은 offline dynamic connectivity라고 불리는 거 같습니다.

관련 문제 링크

https://www.acmicpc.net/problem/16911

16911번: 그래프와 쿼리

 

 

 

UnionByRank를 사용하지 못하는 경우 (대표를 임의로 선택해야하는 경우)

https://eastplanet.tistory.com/212

[백준] 10775번 공항 JAVA

 

 

 

유니온 파인드 예제

https://eastplanet.tistory.com/213

[백준] 3197번 백조의 호수 JAVA