[JAVA] 서로소 집합(Disjoint Sets)과 연산

최근 알고리즘 문제를 풀면서 최소 신장 트리 개념에 대해 공부하다가 알게 된 크루스칼 알고리즘에서 이용되는 서로소 집합과 연산에 대해 정리해보겠습니다.

일단, 서로소는 공통으로 포함하는 원소가 없는 두 집합의 관계입니다. 아래와 같이 A, B 집합이 있을 때, 두 집합에서 공통되는 원소가 없다면 'A와 B는 서로소이다' 라고 말할 수 있습니다.

서로소 관계

 

서로소 집합에서 연산은 크게 3가지가 있습니다.

[ Make-Set 연산 ]
>> 자기 자신인 집합을 하나 만듭니다. 즉, 자기자신이 대표원소가 됩니다. 여기서 대표원소는 부모노드가 자기자신일 때입니다. 예를 들어, 0부터 5까지 Make-Set 연산을 하게 되면 아래 그림과 같습니다.
      Make-Set(0) ~ Make-Set(5)

Make-Set 연산

[ Union-Set 연산 ]
>> 합집합 연산으로, 서로 다른 두 개의 집합을 병합함으로써 부모 링크를 바꾸어주게 됩니다. 예를 들어, 아래와 같이 Union-Set 연산을 하게 되면 그림과 같습니다.
      Union-Set(2, 3) : 3의 부모 링크가 2를 가리키도록 함
      Union-Set(4, 5) : 5가 4 라는 대표원소를 가리키도록 함

Union-Set 연산

     
Union-Set(3, 5) : 3이 있는 집합과 5가 있는 집합을 합함. 결국, 3의 대표원소와 5의 대표원소가 같아져야 함

Union-Set 연산

[ Find-Set 연산 ]
>> 원소가 어느 집합에 속해 있는지 찾습니다. 같은 집합에 속해 있으면 대표원소, 즉 부모 노드가 동일하게 됩니다.
      Find-Set(3) : return 2
      Find-Set(5) : return 4

 

자바에서 위의 세 연산을 구현해보겠습니다. 먼저 Make-Set 연산에서는 0부터 5까지 자기 자신을 가리키게 되므로, 아래와 같이 작성합니다.

public static void main(String[] args) {
	int[] set = new int[5];
    
    for (int i=0; i<5; i++) {
    	set[i] = i;
    }
}

Union-Set(parent, 2, 3), Union-Set(parent, 4, 5), Union-Set(parent, 3, 5) 연산 등을 하려면 아래와 같이 해주면 됩니다. 이 경우, 원소의 값이 더 작은 쪽으로 합치도록 구현하였습니다.

public static void union(int[] parent, int a, int b) {
    int a_parent = find(parent, a);
    int b_parent = find(parent, b);
    
    if (a_parent > b_parent) {
        parent[a_parent] = b_parent;
    } else {
        parent[b_parent] = a_parent;
    }
}

현재까지의 상태를 배열로 표시하면 아래와 같습니다. 서로소 집합을 표현한 트리의 배열 형태는 정점과 해당 정점의 부모를 저장하도록 하면 됩니다.

정점	0	1	2	3	4	5
부모	0	1	2	2 (바뀜)	2 (바뀜)	4 (바뀜)

 

Find-Set 연산은 아래와 같이 구현해줍니다. 위의 배열에서 확인할 수 있듯이, find(parent, 3) 은 2를 리턴하고, find(parent, 5) 는 4를 리턴합니다.

public static int find(int[] parent, int i) {
    if (parent[i] == i) { // 자기 자신이면 대표원소, 즉 부모이므로
        return i;
    } else {
    	return find(parent, parent[i]);
    }
}

 

이렇게 서로소 집합과 연산에 대해서 살펴보았습니다. 이 개념은 무방향 그래프에서 사이클 여부를 판단하거나 최소신장트리 (MST) 에서도 크루스칼 알고리즘에서 사용되는 기본적인 내용으로, 잘 알아두면 도움이 될 것입니다. 크루스칼 알고리즘 관련한 문제는 아래 포스트를 참고해주세요 :)

[SWEA] 4006. 고속도로 건설 2 (with JAVA)