알고리즘 - 유니온파인드, 서로소집합 (Unionfind)

서로소 집합에 대한 알고리즘인 유니온파인드를 계속 까먹고, 다른 포스트에서 보면 다양한 방식이 있어, 그때 그때 찾고 적용하면 햇갈릴 때가 많다. 그래서 내가 쓰는 알고리즘 형식을 메모하기 위해서 유니온파인드 알고리즘을 포스팅한다.

 

개념

서로소 또는 상호배타 집합들은 서로 중복 포함된 원소가 없는 집합들이다.

다시 말하자면 교집합이 없다는 뜻이다.

 

그리고 집합에 하나의 특정 멤버를 통해 각 집합들을 구분한다.

 

서로소 집합을 표현하는 방법은 다음과 같다.

• 연결 리스트
• 트리

그리고 서로소 집합 알고리즘을 적용하기 위해서는 다음과 같은 연산이 필요하다.

• Make-Set(x) : 자신이 대표자가 되어 집합을 만드는 함수.
• Find-Set(x) : 원소 x가 속해있는 집합에서 대표자가 누구인지 찾는 함수.
• Union(x, y) : x가 속한 집합과 y가 속한 집합을 합치는 함수.

다음 그림과 함수적용 예시를 보면 이해가 된다.

 

1. Make-Set(x);  

2. Make-Set(y);

3. Make-Set(a);

4. Make-Set(b);

5. Union(x, y);

6. Union(a, b);

7. Find-Set(y);

8. Find-Set(b);

9. Union(x, a);

 

 

위의 로직을 따라해보면 1,2,3,4는 자기 자신이 대표자가 되어 집합을 형성하고, 그 이후 유니온 함수를 통해 x,y 와 a,b 이렇게 두개의 집합으로 만들어진다.

7번 함수를 통해 y의 대표자는 x이니 x가 출력될 것이고, 8번은 a가 출력될 것이다.

9번 함수를 통해 결과적으로 대표자가 x인 하나의 집합으로 합쳐진다.

 

유니온파인드의 개념적 설명은 여기까지가 끝이다. 다음으로는 자바를 통해 어떻게 유니온파인드를 구현하는지 보여주겠다.

자바 구현

구현은 배열을 사용해서 구현한다.

static void makeSet() {
	for(int i = 0; i < n; i++) {
		arr[i] = i;
	}
}

static int findSet(int x) {
	if(x == arr[x]) {
		return x;
	}
	
	return findSet(arr[x]);
}

static void union(int x, int y) {
	if(x != y) {
		arr[findSet(y)] = findSet(x);
	}
}

 

딱히 어려운 내용은 없어서 자세한 설명은 건너뛰겠다.

 

이 코드를 보고, 개념을 보았을 때 하나 이상한 점이 존재한다. 최적화가 덜 되었다는 것이다.

 

만약 이 그림처럼 Find-Set(b)라는 연산을 하게 되면 재귀 호출을 F가 나올 때 까지 계속 할 것이다. 생각해보자 이 집합에 대한 find-set 연산을 할때마다. 봤던 길과 부모들을 계속 보게될것이다.

 

이러한 최적화를 위해서 다음과 같은 방법이 있다.

• Rank를 이용한 Union
• Path Compression (경로 압축)

경로 압축 방법으로 알려주겠다. 

경로 압축으로 최적화 하는 방법은 아주 간단하다. Find-Set연산을 하여 재귀 호출을 하면서 최상위 부모를 찾을 것인데, 이때 Memonization 기술을 활용해서 기록만 해두면 된다.

 

즉 아래의 코드처럼 고치면된다.

 

static int findSet(int x) {
	if(x == arr[x]) {
		return x;
	}
	
	return arr[x] = findSet(arr[x]);
}

 

이러면 유니온 연산자를 통해서 findset 메소드를 호출 할 것이고 집합의 대표자가 배열 arr에 저장될 것이다.

 

끝.