[알고리즘] UNION-FIND 자료구조

UNION-FIND

유니온 파인드 자료구조는 '합집합 찾기'로 번역할 수 있다.
해당 자료구조에는 2가지 메서드가 있는데 기능은 아래와 같다.

1. Void UNION(int a, int b)
   • 원소 a, b를 하나의 집합으로 합침
2. int FIND(int a)
   • 원소 a의 최상단 부모가 누구인지 판별

구현

초기의 각 원소의 부모노드 배열을 구성한다.
초기에는 집합이 존재하지 않으므로 각 원소의 부모 노드는 자기 자신이 된다.

FIND 함수

Find 함수는 앞서 설명하였듯이 특정 노드의 최상단 부모를 리턴한다.
또한 모든 노드들의 부모를 최상단 부모로 업데이트 시켜준다.

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

UNION 함수

UNION 함수는 앞서 설명하였듯이 두 개의 원소의 집합을 하나의 집합으로 합쳐준다.
이때, 최상단 노드는 a의 최상단 부모 노드가 된다.

public void union(int a, int b) {
	a = find(a);
    b = find(b);
    if (a != b) 
    	parent[b] = a;
}