[Algorithm] 유니온 파인드(Union-Find) 알고리즘

 

 

 

 

유니온 파인드(Union-Find)

• 그래프/트리의 대표적인 알고리즘이다
• 상호 배타적 집합(Disjoint-set)이라고도 부른다
  • 하나의 원소가 둘 이상의 집합에 속하지 않는 서로소 집합으로 표현하기 때문이다
• 여러 노드가 있을 때, 두 노드가 같은 그래프(집합)에 속해 있는지 판별하는 알고리즘이다
• union 연산과 find 연산으로 이루어져 있다
  • union 연산 : 두 원소가 속한 각 집합을 합치는 연산
  • find 연산 : 주어진 원소가 포함된 집합의 부모 노드를 구하는 연산
• 시간복잡도 : O(log N)
  • 평균적으로 트리의 높이만큼을 탐색한다

 

 

Union 연산

다음과 같은 두 집합이 있다고 하자.

집합은 모두 대표노드가 존재하며, 대표 노드는 집합에서 최종 부모 노드, 즉 가장 값이 작은 노드이다.

따라서 노드 1, 2, 3으로 이루어진 집합의 부모 노드이자 대표노드는 1이며, 1의 부모 노드는 자기 자신이다.

노드 4와 5로 이루어진 집합의 부모 노드이자 대표노드는 4이며, 4의 부모 노드 역시 자기 자신이다.

 

각 원소의 부모 노드를 저장하는 parent 배열을 확인해보면 그림과 같다.

 

 

 

만약, union(2,5) 연산을 하게 된다면, 2의 대표노드 1과 5의 대표노드 4 중 더 작은 값은 1이므로 1이 합쳐진 집합의 대표노드가 될 것이다.

즉, 대표노드(부모노드)가 1인 집합과 4인 집합의 두 집합을 합친다(union)면 더 작은 노드를 기준으로 합쳐지게 된다.

따라서, 4의 부모노드가 1로 바뀌게 되므로 parent[4]의 값이 1로 바뀌어 저장되게 된다.

5의 부모노드(parent) 값은 변화가 없지만, 5의 부모 노드인 4의 부모 노드가 1로 바뀌었으므로 대표노드는 1로 바뀐 것이 된다.

 

 

 

Union 연산을 코드로 구현하면 다음과 같다.

public static boolean union(int x, int y) {
	x = find(x); //x의 부모노드
	y = find(y); //y의 부모노드
    
	// 같은 그래프일 때
	if(x == y) return false;
	
    //x의 값이 y보다 작다면, 더 작은 값 x가 y 집합의 대표노드가 된다.
	if(x <= y) parent[y] = x;
	else parent[x] = y;
	return true;
}

 

 

 

 

Find 연산

원소 x가 속한 그래프(집합)을 확인한다고 하자.

이 때, 모든 집합은 집합의 부모 노드로 대표된다.

따라서 parent[x]를 확인해 x 원소의  부모 노드를 확인한다.

만약, parent[x]의 부모 노드가 자기 자신이라면, parent[x]가 x가 속한 집합의 대표 노드이다. 다르다면, 부모 노드를 계속 찾아 올라가야 한다.

이렇게 해서, find 연산은 최종적으로 대표 노드(부모 노드가 자기 자신일 때)를 반환한다.

 

 

find 연산을 코드로 구현하면 다음과 같다.

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

 

 

 

 

참고자료
https://kistone.tistory.com/58
https://velog.io/@suk13574/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98Java-%EC%9C%A0%EB%8B%88%EC%98%A8-%ED%8C%8C%EC%9D%B8%EB%93%9CUnion-Find-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98