[알고리즘] Union Find(서로소 집합)란?

 

✔️ Union Find란?

Union Find(서로소 집합)는 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조라고할 수 있다. Union Find 자료구조를 사용하면 각 Data들이 같은 그룹에 속해있는지, 다른 그룹인지 확인할 수 있다. 즉 서로소 집합은 교집합이 공집합인 집합(서로 집합)들의 정보를 확인(Find)하고, 조작(Union)할 수 있는 자료구조이다.

 

그렇다면 왜 Union Find 자료구조를 사용할까❔

Data들이 어떤 조직에 속하는지 관리하기 쉬우며, 빠른 속도로 조직을 통합 처리 가능하다.

✔️ Union Find 자료구조의 조직 관리 방법

같은 트리에 묶여있으면 같은 그룹이라고 간주한다.

아래 트리에서 (A,B,C,D) (E,F,G) (H,I) 는 그룹이다.

 

부모 자식 순서는 상관없다. 그룹인지 아닌지 구분만 중요하다.

예를 들어 아래 트리는 모두 같은 그룹 상태를 나타낸다.

 

 

이때 Max Level이 작을 수록 자료구조 속도가 빠르고, 따라서 세번째 트리가 가장 빠른 형태이다.

 

트리는 1차원 배열의 DAT 형태로, 자신의 부모가 누군지만 기록한다.

아래 그룹의 최상위 부모인 A는 이 그룹을 대표하는 Root이다.

✔️ Union Find의 두가지 함수

Union 역할을 하는 함수 : insert(a, b);

b그룹을 a그룹에 속하도록 한다. -> b의 root의 부모가 a의 root가 되도록 수정

 

 

💡구현

ch1과 ch2의 root를 각각 구한다. 이때, root가 같다면(이미 같은 그룹이라면) 아무것도 하지 않는다.

ch2 그룹이, ch1 그룹 안에 속하게 하기 위해 ch2 root의 부모를 ch1 root로 설정한다.

char parent[200];

void insert(char ch1, char ch2)
{
	int a = getParent(ch1);
	int b = getParent(ch2);
	if (a != b) parent[b] = a; //ch2의 그룹이 ch1의 그룹에 속하도록
}

 

Find 역할을 하는 함수 : p = getParent(a);

최상위 부모(root)를 찾아서 return 한다.

 

💡구현

최상위 부모(root)를 찾기 위해, 재귀를 통해 계속 부모 노드를 탐색한다.

더 이상 부모가 없는 (root인) ch까지 도달했을 때의 ch값을 return한다.

char parent[200];

char getParent(char ch)
{
	if (parent[ch] == 0) return ch; //자신이 root인 경우
	return getParent(parent[parent[ch]]); //재귀로 root 찾기
}

앞서 설명했듯이, Max Level이 작을 수록 자료구조 속도가 빠르다.

따라서 더 빠른 성능을 원한다면, getParent 함수에서 return될 때,

탐색되는 노드들의 부모를 root로 바꿔줌으로써 경로를 압축할 수 있다.

 

char getParent(char ch)
{
	if (parent[ch] == 0) return ch; //자신이 root인 경우
	return parent[ch] = getParent(parent[ch]); //재귀로 root 찾기, root 바꾸기
}

Union Find를 활용한 문제(예시)와 풀이는 다음에서 확인할 수 있다.

👉 https://nayoungs.tistory.com/entry/C-%EB%B0%B1%EC%A4%80-1976-%EC%97%AC%ED%96%89-%EA%B0%80%EC%9E%90-feat-Union-find

(C++) 백준 1976 : 여행 가자 (feat. Union-find)