[알고리즘] 분리집합 (Union Fnd)

어떤 문제에서 적용?

• 동일 부류인지 확인할 때
• 동일 부류가 아닌지 확인할 때
• 총 몇 개의 묶음인지 확인할 때

분리집합이란?

교집합이 존재하지 않는 둘 이상의 집합

 

분리집합을 만들어가는 과정, 그리고 코드 작성하기

1. 해야할 것 첫번째, 내가 가리키는 부모의 숫자를 저장하자.

// 초기화 과정
int p[10001];
for(i=1; i <= 1000; i++) p[i] = i;

2. 3번 4번 노드가 같은 집합에 있음을 어떻게 알까? 4번 7번 노드가 같은 집합에 있음을 어떻게 알까? 이것은 재귀적으로 부모의 부모를 계속 탐색하는 과정이다.

int find(int n){
	if(p[n] == n) return n; 
  	return find(p[n]); 
}

 

하지만 이 경우 최악의 경우에는? 만약 이런 경우를 생각해 보아라.

부모를 찾기 위해 최대 O(N)이 걸릴 수 있다.

// 평균적으로 O(log n) 하지만 최악의 경우에는 O(n)이 된다. 
// 더 효율적으로 압축할 수 있는 방법은? -> 메모이제이션을 사용하여 무려 [거의 O(1)]이 가능하다 
int find(int n){ 
	if(p[n] == n) return n; 
    return (p[n] = find(p[n])); //경로 압축 
}

3. 두 집합을 하나의 집합으로 합치는 과정

void union(int i, int j){ 
	// i와 j에는 이미 경로압축이 다 되었음 
    p[p[j]] = p[i]; 
}

if(find(i) != find(j)) union(i,j);

백준 풀어 볼 만한 문제

1717번 집합의 표현 : 기본 문제

1043번 거짓말 : 기본 문제

1976번 여행 가자 : 기본 문제

4195번 친구 네트워크 : 맵 자료구조를 이용

 

뽀나스로

이런 문제에서도 분리 집합을 사용할 수 있다. 다음과 같이 코드를 작성할 수 있다.

예) 머머가 있다. 머머는 총 몇 개의 집합으로 되어 있는가?