유니온 파인드(Union Find)

설명

---

유니온 파인드는 집합의 표현을 빠르게 구현하는 알고리즘이다.

 

예를 들어보자.

사람 P1, P2, P3, P4가 있다. 각 사람은 자신의 소속집단 C1, C2, C3, C4에 가입되어 있다고 가정하자.

 

1. C3에 속한 P3가 P1과의 합병을 진행한다. 

그렇다면 P1, P2, P3, P4의 각 소속집단은 C1, C2, C1, C4으로 바뀔 것이다.

 

2. C1에 속한 P1이 P4와의 합병을 진행한다.

그렇다면 P1, P2, P3, P4의 각 소속집단은 C4, C2, C4, C4으로 바뀔 것이다.

 

2번 과정에서, P1(C1)과 P4(C4)의 병합을 위해 C1소속 사람과 C4소속 사람의 합병이 진행되었다.

이로인해 C1에 소속이었던 P3의 소속집단도 C4로 변한것을 확인할 수 있는데, 이 방법은 최악의 경우 모든 경우에 대해 O(N)이 소요될 수 있다.

 

이러한 요소들이 많아졌을 때, 소속 집단을 합치고, 어떤 요소가 어디에 소속되어있는지를 O(N)보다 빠르게 찾기위한 알고리즘이 바로 유니온 파인드이다. 

 

 

예제를 들어 더 쉽게 알아보자.

예를 들어 arr[5] = {0, 1, 2, 3, 4}가 있다고 가정하자. 각 요소의 부모를 P로 표현하고 P[i] = i 라고 하자.

0과 1을 합치게 되면 1의 부모를 0의 부모로 바꾼다.

2와 3을 합치고, 3과 4를 합치면 다음과 같다.

만약 이 시점에서 0과 2를 합치고 싶다면 어떻게 해야할까? 

부모가 2인 집단에 포함되어있는 모든 요소의 부모를 0으로 바꿔야할까?

 

시간이 중요한 우리에게 이 작업은 너무 오래걸려 매력적이지 못한다. 위 과정은 합병하는 과정에서 O(N), 부모를 찾는 과정에서 O(1)이 소요될 것으로 예상할 수 있다. 

각각 O(N), O(1)이 걸리는 과정을 O(logN), O(logN)으로 치환할 수 있다면 매력적일 것이다.

 

유니온 파인드의 과정을 따르면, 이 상황에서 0과 2를 합친다면 2의 소속집단을 0의 소속집단으로 바꿔주기만 하면 된다. 

그러면 위와 같이 바뀔 것이다. 이 상황에서 만약 4의 소속집단을 찾고싶으면 재귀를 사용하면 된다.

4의 현재 부모는 2로 되어있으니 2의 부모를 찾는다. 2의 부모는 0으로 되어있으니 0의 부모를 찾는다.

0의 부모는 0이다. 즉, index와 P[index]가 서로 같다. 이때 리턴하고 저장해주면 된다.

 

 

각 집단의 대표요소의 부모만 바꿔주어도 각 요소의 부모를 정확히 찾을 수 있다는 점에 주목해야 한다.

 

구현

---

찾는 함수(find)와 합병 함수(merge)의 구현이 필요하다.

void initialize(){
    for(int i=0; i<N; i++){
        p[i] = i;
    }
}

int find(int a) {
	if (a == p[a]) return a;
	return p[a] = find(p[a]);
}

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

 

시간 복잡도

---

위 과정을 통해 전체 요소와 부모를 트리형태로 생각할 수 있다. 요소 N개에 대해 트리의 높이는 logN이므로, find와 merge 함수의 시간복잡도는 O(logN)으로 표현할 수 있다.

 

 

추천문제

---

 

유니온파인드 기본예제

1717번: 집합의 표현

1976번: 여행 가자

20040번: 사이클 게임

 

응용 심화 문제

1197번: 최소 스패닝 트리

10775번: 공항

3197번: 백조의 호수

 

 

 

알아두면 매우 요긴하게 사용할 수 있다.

최근에 실시된 2023 카카오 블라인드 1차 코테에서 2차원 배열에 대한 유니온 파인드 문제가 출제되었다.