[알고리즘] 유니온 파인드 (Union-Find) 개념과 최적화 기법

유니온 파인드 개념

상호 배타적 부분 집합(Disjoint Set : 서로소 집합)을 표현할 때 사용

여러 노드가 존재할 때 두 노드를 같은 집합으로 묶어주고 같은 집합에 속하는지 판별

 

연산

•Union (합집합) : 노드 x가 포함된 부분 집합과 노드 y가 포함된 부분집합을 합치는 연산

•Find (x): 노드 x가 포함된 부분집합을 찾는 연산

 

최적화 기법

1. Path Compression

2. Union by Rank (Union by Height)

3. Weighted Rule (Union by Size) 

 

유니온 파인드구현

초기화

부모 노드를 지정할 parent 배열 선언 (코드로 구현할땐 편하게 p로 선언하겠다)

parent를 자기 자신으로 지정하여 초기화

n개의 원소가 각각 하나의 부분집합 이룸

for(int i=0; i<=n; i++)
	parent[i]=i;

Idx	1	2	3	4	5	6	7
P[i]	1	2	3	4	5	6	7

 

각자 하나의 부분집합으로 존재하는 상태를 그림으로 구현하면 다음과 같다.

유니온파인드 설명 그림 1

 

여기서 1~3을 연결하고 5와 6을 연결해서 각각 하나의 부분집합으로 만들어보자

유니온파인드 설명 그림 2

유니온 파인드 설명 그림 3 그림을 직접 만들다보니 좀 삐뚤어졌다..

Idx	1	2	3	4	5	6	7
P[i]	1	1	2	4	5	5	7

p[i] = i 인 경우(부모가 없는 경우)인 1,4,5,7은 루트 노드이다. -> 4개의 부분 집합(트리) 존재

3의 부모는 2이고, 2의 부모는 1이다. 1은 루트 노드이다.

6의 부모는 5이다. 5는 루트 노드이다.

-> 3과 6은 연결되어 있지 않다. (서로 다른 부분집합에 속해있다.)

 

이 상태에서 코드로 구현해보면 다음과 같다. 

1. Find 연산 구현

int find(int n){
    if (p[n] == n) return n;//루트노드이면 리턴
    else return find(p[n]);
}

자신의 부모를 따라 루트 노드를 찾아 돌려줌으로써 자기가 속한 집합을 알아내는 함수이다. 

parent[n] = n이 될때까지, 루트노드를 찾을때까지 재귀함수로 푸는 것이다. 

재귀함수에 대한 개념을 알고 싶다면 여기를 클릭

 

2. Union 연산 구현

void merge(int a, int b){
    a = find(a);
    b = find(b);
    if (a==b) return;
    else p[b] = a;
 }

a가 속한 부분집합과 b가 속한 부분집합을 알아낸다. (find 함수)

리턴 값(루트)가 같다면 둘이 속한 부분집합이 같다는 뜻이므로 합칠 필요가 없다. 

다르다면 b의 부모를 a로 만들어주면서 둘을 합친다. 

 

여기서 유니온 파인드 최적화 기법 1번을 적용한다면 더 효율적으로 구현할 수 있다! 

앞부분 초기의 부분 상태를 다시 가져와보자

유니온파인드 설명 그림 4

내가 만약 여기서 1~6을 모두 연결하고 싶다면 이런 그림이 된다. 

유니온 파인드 설명 그림 5

Idx	1	2	3	4	5	6	7
P[i]	1	1	2	3	4	5	7

루트가 한쪽으로 치워질 경우 재귀 함수를 통해 루트 노드를 찾을 때 탐색 시간이 오래 걸릴 수 밖에 없다. 

여기선 1~6을 합쳤지만 만약 1~7까지 모두 합친다면 7에서 1를 찾을때까지 O(7)시간이 걸리는 것이다.

숫자로 표현하니 시간이 짧은 것 처럼 느껴지는데.. 이걸 n이라 생각하면 총 O(n) 시간이 걸린다. 

이걸 해결하기 위해선 어떻게 표현하면 좋을까? 

인접한 부모 노드의 번호가 아닌 ‘루트 노드 번호’ 지정하면 된다. 

 

유니온 파인드 설명 그림 6 좀 징그럽게 표현되었다

Idx	1	2	3	4	5	6	7
P[i]	1	1	1	1	1	1	7

이렇게 표현하면 7에서 1을 찾을때도 바로 찾을 수가 있다. 

이처럼 더 짧은 경로를 찾아 트리의 높이를 낮춰 연산 속도를 높이는 것이다.

이걸 코드로 구현하면 아까의 find 함수에서 부모 노드를 따라 올라갈때 모두 루트노드로 대입해주면 된다 . 

int find(int n){
    if (p[n] == n) return n;
    else return p[n] = find(p[n]);//부모 노드를 루트 노드로 바꿔준다
}

find(𝑥)를 수행할 때 𝑥에서 루트까지 가는 경로 상에 있는 노드를 모두 루트의 자식 노드로 만드는 기법이 Path Compression (경로 압축) 이다.

그럼 아까 만들었던 1~3 부분집합과 5,6 부분 집합도 이렇게 표현할 수 있을 것이다. 

유니온 파인드 설명 그림 7

idx	1	2	3	4	5	6	7
p[i]	1	1	1	4	5	5	7

여기서 1과 5를 연결하면? 다음과 같은 트리가 완성된다!

유니온 파인드 설명 그림 8

idx	1	2	3	4	5	6	7
p[i]	5	1	1	4	5	5	7

왜 2와 3의 부모도 5로 바뀌는 것이 아닌 1의 부모만 바뀌는 거냐 생각할 수도 있는데 당연하다. 

find(1) 함수를 실행하여 1의 부모를 바꾸는 연산을 수행했기 때문이다. 

만약 find(2)를 실행했다면 2의 부모, 1의 부모가 모두 5로 바뀌었을 것이다. (3의 부모는 그대로 1)

 

여기까지 이해했으면 유니온 파인드의 기본 개념은 다 숙지한 것이다. 

 

그래도 아쉬우니 나머지 최적화 기법도 간단하게 보고 넘어가자

1. Union by Rank (Union by Height)

더 낮은 랭크(높이)의 트리를 더 높은 랭크(높이)의 트리에 병합하여 트리의 균형을 유지하는 기법

2. Weighted Rule (Union by Size)

더 작은 크기의 집합을 더 큰 크기의 집합에 병합하여 효율성을 높이는 기법

 

글로 쓰다보니 좀 헷갈리게 적은 거 같은데 요점만 보면 

Union by Rank에선 높이가 기준이고 Weighted Rule(가중 법칙)에선 크기가 기준이다.

 

 

유니온 파인드 최적화 기법 구현

 

트리의 사이즈가 큰 쪽에 낮은 쪽의 루트를 붙여 병합한다.

두 트리를 비교하기 위해서 rank라는 배열 사용. 

rank가 더 낮은 쪽이 큰 쪽의 자식이 됨

(rank를 사용하려 했으나 c++ 기본 내장 함수로 인해 ran으로 구현하였다) 

 

1. Union by Rank (Union by Height)

높이가 더 높은 루트에 더 낮은 집합의 루트를 자식으로 연결

트리의 높이가 큰 쪽을 루트를 붙임

rank 배열에 트리의 높이 지정

void merge(int a, int b){
    a = find(a);
    b = find(b);
    if (a==b) return;
    if (ran[a] < ran[b])
    	swap(a,b)
    p[b] = a;
    if (ran[a] == ran[b]) ran[a] ++;
 }

높이가 더 큰 쪽에 붙였으므로 전체 높이에선 차이가 안난다. 

그러나 만약 트리의 높이가 같다면 자식이 하나 더 생겼으므로 높이를 추가 해줘야 한다. (ran[a] ++) 코드

 

2. Weighted Rule (Union by Size)

더 큰 집합의 루트에 크기가 작은 집합의 루트를 자식으로 연결

트리의 사이즈가 큰 쪽을 루트로 작은 쪽을 붙임

rank 배열에 트리의 사이즈(=노드 수) 지정

void merge(int a, int b){
    a = find(a);
    b = find(b);
    if (a==b) return;
    if (ran[a] < ran[b])
    	swap(a,b)
    p[b] = a;
    ran[a] += ran[b];
 }

방금전 코드와 달라진 점을 보면 ran[a] += ran[b]; 가 보인다. 

ran[n]함수 안에 각 부분 배열의 크기 값이 들어있으므로 이것은 b의 크기를 a에 더해주는 코드이다. 

 

유니온 파인드의 시간 복잡도

1. Find 연산

최악의 경우 O(n), 최적화된 구현으로 O(log n)까지 가능

2. Union 연산

최악의 경우 O(n), 최적화된 구현으로 O(1)까지 가능

 

---

풀어보면 좋을 백준 문제

1717 집합의 표현

1976 여행가자

10775 공항

1043 거짓말

20040 사이클 게임