Algorithm 16일차

알고리즘에서 서로소 집합을 활용할 수 있다.

서로 교집합이 없는 집합들을 서로소 집합이라고 한다.
각 집합들 중 하나의 특정 멤버를 대표자라고 한다.

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

1. Make-Set(x) : x 요소가 유일한 멤버인 집합을 만든다. (x가 대표자인 집합)
2. Union(x, y) : x 요소가 포함된 집합과 y 요소가 포함된 집합을 합친다.
   이 때, x 요소가 포함된 집합과 y 요소가 포함된 집합이 겹치는 지 Find-Set() 으로
   확인한 후 안 겹칠 시 Union(x, y)를 실행한다.
   집합이 합쳐지면 x 요소가 포함된 집합의 대표자가 전체 집합의 대표자가 된다.
3. Find-Set(x) : x 요소가 포함된 집합의 대표자를 반환한다.

서로소 집합은 연결리스트로 표현할 수 있다. 규칙은 아래와 같다.

1. 같은 집합의 원소들은 하나의 연결리스트로 관리한다.
2. 연결리스트의 맨 앞의 원소는 집합의 대표 원소이다.
3. 각 원소는 집합의 대표 원소를 가리키는 링크를 갖는다.

아래 그림을 참고하자.

서로소 집합을 구현하면 아래와 같다.

import java.util.Arrays;

public class UFTest {
	static int[] p;
	static int N;
	
	public static void makeSet() {
		for (int i = 0; i < N; i++) {
			p[i] = i; // 자기가 자기자신을 가리킨다.
		}
	}
	
	public static int findSet(int x) {
		if (p[x] == x) {
			return x;
		}
		
		return p[x] = findSet(p[x]);
	}
	
	public static void unionSet(int a, int b) {
		p[findSet(b)] = findSet(a);
	}
	
	public static void main(String[] args) throws Exception {
		N = 7;
		p = new int[7];
		
		makeSet(); // 집합 만들기
		System.out.println(Arrays.toString(p));
		
		unionSet(1, 4); // 집합 합치기
		System.out.println(Arrays.toString(p));
		
		unionSet(2, 3); // 집합 합치기
		System.out.println(Arrays.toString(p));
		
		unionSet(2, 4); // 집합 합치기
		System.out.println(Arrays.toString(p));
		
		System.out.println(findSet(1)); // 대표자 출력
		System.out.println(findSet(4)); // 대표자 출력
	}
}

출력 결과는 아래와 같다.

[0, 1, 2, 3, 4, 5, 6]
[0, 1, 2, 3, 1, 5, 6]
[0, 1, 2, 2, 1, 5, 6]
[0, 2, 2, 2, 1, 5, 6]
2
2