Disjoint Set (분리 집합)

Disjoint Set

분리 집합 또는 서로소 집합은 각각의 집합이 공통 원소를 가지고 있지 않은 집합이다. 즉 전체집합 U에 대해, U의 분리 집합 A ,B는 다음 조건을 만족한다.

• A, B는 U의 부분 집합이다.
• A, B는 공통 원소를 가지지 않는다. (A ∩ B = Ø)
• A, B의 합집합은 전체 집합 U이다. (A ∪ B = U)

위 조건은 분리 집합이 개수가 3개 이상일때도 만족한다.

Disjoint Sets

Union-Find

Union-Find는 분리 집합을 구현하고 조작하는 자료구조이다. 분리 집합을 합치는 연산인 union 연산과 임의의 원소가 어떤 집합에 속하는지 찾는 find 연산을 제공한다해서 union-find 자료구조라 불린다. Union-Find를 구현하기 위해선 아래 3가지 연산을 구현해야한다.

• 초기화 : 초기 n개의 원소가 있을 때, 자신만을 갖는 n개의 분리 집합 생성
• union 연산 : 두 원소 a, b가 주어질 때 이들이 속한 두 분리집합을 합침
• find 연산 : 어떤 원소 a가 주어질 때 이 원소가 속한 집합 반환

분리 집합을 아래와 같이 트리로 표현한다. 트리로 표현하면 union 연산과, find 연산을 효율적으로 수행할 수 있다. 트리의 루트노드가 집합명(집합을 구분하는 key)이다. 현재 1번 집합과 4번 집합이 있으며 1, 2, 3번 노드는 1번 집합에 4, 5, 6번 노드는 4번 집합에 속해있다.

Find(5) : 5번 노드가 속한 트리의 루트 노드를 반환한다. 즉 4가 반환된다. 만약 트리가 깊다면 한번의 동작으로 루트 노드를 구할 수 없다. 따라서 재귀적으로 구현한다.

 

Union(2,5) : 2번 노드가 속한 트리와 5번 노드가 속한 트리를 합친다. 즉 find 연산으로 2번 노드와 5번 노드의 루트 노드를 구한다음 아래와 같이 자식 노드로 설정해주면 된다.

find 연산의 시간 복잡도는 해당 노드에서 루트 노드까지 이동하는 것이므로 O(트리 depth)만큼의 시간 복잡도가 든다. 아래 나올 최적화까지 진행한다면 최소 O(1), 최대 O(트리 depth)의 시간 복잡도가 든다. union 연산의 시간 복잡도는 두 번의 find 연산을 진행 한 후 단순히 루트 노드들을 이어주는 것이므로 O(find 연산 시간 복잡도 x 2), 즉 최소 O(1), 최대 O(트리 depth)만큼의 시간 복잡도가 든다. 결국 union-find을 효율적으로 수행하려면 집합 트리의 depth를 최대한 작게 만들어야한다.

구현

/***
 * 분리 집합은 트리로 표현하며, 트리의 루트 노드가 집합명.
 */

public class DisjointSet {

	static int[] parent;
	
	public static void main(String[] args) {
    	//초기화, n개의 분리 집합을 만듬
		parent = new int[7];
        for(int i=1; i<=6; i++) parent[i]= i;

        //union 연산, 1번 집합 = {1, 2, 3}
        union(1, 2);
        union(2, 3);
        System.out.println("1번 집합 : " + find(1) + " " + find(2) + " " + find(3));

        //union 연산, 4번 집합 = {4, 5, 6}
        union(4, 5);
        union(5, 6);
        System.out.println("4번 집합 : " + find(4) + " " + find(5) + " " + find(6));

        //union 연산
        union(2,5);

        //결과 확인
        System.out.println("결과 : " + find(1) + " " + find(2) + " " + find(3) + " " + find(4) + " " + find(5) + " " + find(6));
    }
	
	//y 노드가 속한 트리의 루트 노드가 x 노드가 속한 트리의 루트 노드의 자식이 됨
	static void union(int x, int y) {
		int rootX = find(x);
		int rootY = find(y);
		
		parent[rootY] = rootX;
	}
	
	//x 노드가 속한 트리의 루트 노드를 반환 (재귀 구현)
	static int find(int x) {
		if(parent[x] == x) return x;
		
		parent[x] = find(parent[x]); //최적화로 트리 깊이를 줄임
		return parent[x];
	}
}

find 함수는 x 노드에서 루트 노드까지 이동해 루트 노드를 반환한다. 그래서 find 함수를 재귀로 구현했다. 여기서 최적화를 진행한다면 위 코드처럼 parent[x]의 값이 루트 노드가 아니면 루트 노드로 설정해주는 코드를 넣는다. 즉 트리에 속한 노드의 부모는 루트 노드가 되도록 만든다. 이럼으로써 트리의 깊이를 낮게 만들어 find 연산의 수행 속도를 높일 수 있다. 또한 트리를 parent[] 배열로 구현했다는 점에 주목하자. 각 노드는 부모 노드의 포인터를 가질뿐 자식 노드의 포인터를 가지지 않는다. 왜냐하면 union, find 연산 시 자식 노드로 이동할 일이 없기 때문이다. 

그래프에서의 Union-Find

그래프에서 Union-Find 자료구조는 노드들이 같은 그래프에 속하는지 알고자 할때 많이 사용한다. 즉 하나의 그래프를 하나의 분리 집합이라 보고 Union-Find 자료구조를 적용해 노드가 어떤 그래프에 속하는지 효율적으로 알 수 있다.

 

예를 들어보자. 아래는 6개의 도시를 도로로 연결한 모습이다. 

이때 B 도시와 E 도시가 서로 연결되어 있는지 확인하고 싶다. 어떻게 확인할 수 있을까? 첫 번째 해결책으로 B 노드부터 시작해 그래프 탐색을 하면 된다. 이 경우 시간 복잡도는 O(N)이 된다. 두 번째 해결책으로 Union-Find 자료구조를 적용한다. A, B, C가 하나의 집합이 되고 D, E, F가 하나의 집합이 된다. 따라서 find 연산으로 B와 E가 같은 집합인지 확인하면 된다. 이 경우 시간 복잡도는 최대 O(N), 최소 O(1)이 된다.

가장 큰 집합 추적

union-find 자료구조에 추가적인 정보를 넣으면 union, find 연산말고도 다른 일들을 할 수 있다. 예를 들면 각 집합의 크기를 쉽게 추적할 수 있다. 각 트리의 노드 개수를 담은 배열 size를 추가 한뒤 union 시 이 값을 갱신해주면 된다. 이를 통해 가장 큰 집합의 크기가 어떻게 변하는지 추적하거나, 과반수가 출현하는 시점을 찾는다거나 하는 작업을 간단하게 구현할 수 있다.