티스토리 뷰

프로그래밍/C++

Union-Find

국윤창 2018. 5. 23. 22:48

Union-Find 자료구조는 Disjoint Set이라고도 불리는데, 이 자료구조는 Dijkstra Algorithm, Kruskal Algorithm 등 여러 그래프 알고리즘에서 사용된다. Union-Find 자료구조는 집합을 관리하는 자료구조로 사용된다.

Union-Find 자료구조는 Union과 Find 두 개의 연산을 지원하며 아래와 같다.


* Union: 요소 A가 속한 집합과 요소 B가 속한 집합을 병합한다.


* Find: 요소 A가 주어졌을 때, 이 요소가 속한 집합을 반환한다.


1. 배열로 구현

Array[i] : i 번 원소가 속하는 집합의 번호라고 할 때 연산은 아래와 같다.


* Initialize: 배열을 각자 다른 집합 번호로 초기화 한다.


* Union: 두 집합 A, B를 합치기 위해 배열의 모든 원소를 순회하며 집합 A의 번호를 집합 B의 번호로 바꾼다. (O(N))


* Find: 배열을 참조하면 집합 번호를 바로 알 수 있다. (O(1))


Find 연산이 빠르지만, 보통 Union 연산 수행 횟수가 많으므로 더 좋은 방법을 생각해야 한다.


2. 트리로 구현

집합을 트리로 표현할 수 있다. 트리에는 대표 원소인 root 노드가 존재하므로 root노드를 집합 번호로 생각할 수 있다. 이에 따라 지원하는 연산은 아래와 같다.


* Initialize: 각 원소가 모두 root 노드가 된다. N개의 root 노드를 생성하고, 부모를 가리키는 포인터를 자기 자신으로 설정한다.



* Union: 각 트리의 root 노드를 찾은 후(Find), root 노드가 서로 다르다면 하나를 다른 한 쪽의 자식으로 넣어서 두 트리를 합친다.

[그림 2] Union



* Find: 원소가 포함된 트리의 root 노드를 찾는다.

[그림 3] node 2 Find




Union 연산 수행시간은 Find에 비례하는데, Find 연산은 O(N)보다 작으므로 배열로 구현한 것보다 효율적임을 알 수 있다.

트리로 구현할 때 소스 코드는 아래와 같다.

typedef struct DisjointSet {
	vector<int> parents;		// 각 노드에 대한 부모 노드의 번호

	DisjointSet(int n) 
		: parents(n)
	{
		// 초기화
		for(int i = 0; i < n; i++)
			parents[i] = i;
	}

	int find(int u) const
	{
		if(u == parents[u])
			return u;
		else
			return find(parents[u]);
	}

	void merge(int u, int v)
	{
		u = find(u);
		v = find(v);

		// 집합이 같은 경우 합치지 않는다.
		if(u == v)
			return;

		parents[u] = v;
	}
} DisjointSet;


3. 최적화

트리로 구현했을 때 최악의 경우 완전 비대칭 트리가 되어, 아래 그림 4처럼 연결리스트가 될 수 있다.

[그림 4] Worst Case


원소의 개수가 N이면 트리의 높이가 N - 1이므로, Union, Find 연산의 수행시간이 O(N)이 된다. 이렇게 되면 배열로 구현했을 때 보다도 효율이 나빠진다. 

이 문제는 높이가 더 낮은 트리를 높은 트리 밑에 넣음으로써 해결할 수 있다. 이런 최적화를 union-by-rank 라고 한다. 소스코드는 아래와 같다.

typedef struct OptimizedDisjointSet {
	vector<int> parent, rank;

	OptimizedDisjointSet(int n)
		: parent(n), rank(n, 1)
	{
		for (int i = 0; i < n; i++)
			parent[i] = i;
	}

	int find(int u)
	{
		if (u == parent[u])
			return u;

		// 경로 압축 (path compression)
		// 한 번 경로를 찾으면 다음 번에 또 찾을 필요 없도록 한다.
		return parent[u] = find(parent[u]);
	}

	void merge(int u, int v)
	{
		u = find(u);
		v = find(v);

		// 집합이 같은 경우 합치지 않는다.
		if (u == v)
			return;

		// 트리 높이 비교
		if (rank[u] > rank[v])
			swap(u, v);

		parent[u] = v;

		// 두 트리의 높이가 같으면 결과 트리의 rank++
		if (rank[u] == rank[v])
			rank[v]++;
	}
} OptimizedDisjointSet;

find 함수의 path compression 부분은 한 번 경로를 찾으면 다시 찾을 필요 없도록 하는 부분이다. 아래 그림 5는 원소 8을 Find 할 때 모습을 도시한 것이다.


[그림 5] Path Compression


다이나믹 프로그래밍처럼 한 번 찾은 결과를 다시 찾을 필요가 없도록 하기때문에, 연산을 호출할 때마다 수행시간이 달라진다. (트리의 높이 변화)

평균 수행시간은 O(a(N))으로 a(N)은 아커만 함수를 이용해서 정의되는 함수이다. N이 아무리 크더라도 보통 a(N)은 4이하로 나오므로, 시간 복잡도는 상수나 마찬가지이다.


구현이 간단하고 속도가 아주 빠르므로 다른 알고리즘의 일부분으로 많이 쓰인다.


* 이 자료구조를 사용하여 풀 수 있는 문제들

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

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



* 참고

Union-Find

http://bowbowbow.tistory.com/26


http://weeklyps.com/entry/%EC%9C%A0%EB%8B%88%EC%98%A8-%ED%8C%8C%EC%9D%B8%EB%93%9C-Unionfind


아커만 함수

https://ko.wikipedia.org/wiki/%EC%95%84%EC%BB%A4%EB%A7%8C_%ED%95%A8%EC%88%98

'프로그래밍 > C++' 카테고리의 다른 글

Sort  (0) 2018.05.14
Const Reference  (0) 2017.04.20
Windows C++ RTP Streaming from Cam using FFMPEG and OpenCV  (22) 2017.03.16
댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
«   2024/03   »
1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31
글 보관함