[알고리즘] 유니언 파인드(Union Find)

 

Union Find?

---

Union-Find(혹은 Disjoint Set)은 교집합이 공집합인 집합(서로소 집합)들을 효율적으로 표현하기 위해 만들어진 자료구조이다. 서로 다른 집합을 하나의 집합으로 합치는 Union 연산과 원소가 어떤 집합에 포함되어있는지를 찾는 Find연산으로 이루어져있다. 노드간의 연결관계가 주어졌을 때 그룹 관계를 파악할때 주로 사용한다.

 

코드 (c++)

---

초기화

각 노드들이 자기 자신을 부모(parent)로 가지도록 초기화해준다.

for (int i = 1; i <= n; i++) {
		parent[i] = i;
}

 

find 함수

int find(int x) {
	if (parent[x] == x) return x;
	else {
		return parent[x]=find(parent[x]);
	}
}

find함수는 루트 노드를 찾는 함수이다. 초기화에 의해 parent[x] = x, 즉 자기 자신이라면 루트 노드라는 의미이다. 루트를 찾는 과정에서 경로 압축을 진행하여 수행 시간을 단축한다. 경로 압축이란 아래 그림과 같이 모든 자손들을 직속 자손으로 만들어주는 과정이다. 이 과정을 통해 보다 빠르게 루트 노드를 찾을 수 있게 된다.

 

Union 함수

void merge(int x, int y) {
	int px = find(x);
	int py = find(y);

	if (px != py) {
		parent[px] = py;
	}
}

union함수는 각 원소가 속한 집합을 하나로 합치는 연산이다. 두 노드의 부모들을 확인하다. 이때 두 부모가 같지 않다면 한 집단에 속하지 않음을 뜻한다. 두 집단을 합치는 것은 find함수 덕분에 간단하다. find함수에 의해 구한 한 부모 노드를 다른 부모 노드에 바로 연결하면 된다.

 

예제

---

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

1717번: 집합의 표현