유니온 파인드(Union - Find)

유니온 파인드(Union - Find) or 분리집합 ( Disjoint Set)

상호 배타적으로 이루어진 집합으로 Disjoint-set이라고도 한다. 그래프 알고리즘의 일종이며, 서로 다른 두 개의 집합을 병합하는 Union 연산과 집합의 원소가 어떠한 집합에 속해있는지 판단화는 Find연산을 사용하기 때문에 Union - Find라는 이름이 붙었다.

• 모든 집합들 사이에 공통된 원소가 존재하지 않는다
• 모든 원소들이 자신이 속해있는 유일한 집합만을 가진다.
• 유니온 파인드(Union - Find) 자료구조를 사용하면 서로 다른 원소들이 같은 집합에 속해 있는지, 혹은 속해있지 않은지를 판별하는데 유용하다.

두 축인 Find 와 Union 메소드는 다음과 같다.

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

	private static void union(int a, int b) {
		a = find(a);
		b = find(b);
		
		if(b < a) parent[a] = b;
		if(a < b) parent[b] = a;
	}

• find 메소드는 특정 노드의 root노드를 찾아준다.
• union 메소드는 두 노드를 연결시켜준다.

따라서 각각의 노드들은 자신이 속해있는 그룹의 root에 의해 묶이게된다.

각 노드들의 그룹을 상호 배타적으로 파악할 때에 유용한 자료구조이다.

또한, 아직 그룹핑되어있지 않거나 root노드인 경우에는 스스로 자신을 가르키게 만들어 준다. (parent[i] = i) 그렇게 함으로서 root노드를 판별할 수 있다.