Union-Find 알고리즘

기본 예제

서로 친구이면 하나의 집합으로 묶을 수 있다.

만약 1번과 2번이 친구라면 A = {1, 2}

만약 2번과 3번이 친구라면 B = {2, 3}

이 때 집합 A 와 집합 B에 공통된 원소가 있으면 두 집합을 한 집합으로 본다.

즉 공통원소가 있으면 묶어버린다.

 

Disjoint Set은 공통원소가 없는 서로소 집합을 뜻한다.

Disjoint Set은 내부적으로 트리 구조로 표현한다.

• 각 집합은 하나의 트리
• 트리의 루트가 집합의 대표
• 같은 루트를 가지면 같은 집합

친구일 때마다 트리에 연결하고 그렇게 연결된 노드들은 한 집합이다

위 입력 예제에서는 다음과 같이 트리가 2개 생성

 

코드로 구현

1. 먼저 초기화를 해준다.

for(int i=1; i<=n; i++){
	unf[i]=i;
}

unf은 1차원 배열로 트리를 표현한 것이다. 

각 idx은 학생을 뜻하고 unf에 있는 값은 집합의 번호이다.

처음에는 각자 단독 집합이다.

1번은 1번 집합 2번은 2번 집합.. → 총 9개의 집합 (초기화)

 

2. 친구 정보 하나씩 읽어 드리면서 Union함수로 트리로 서로 묶어준다. ★

for(int i=1; i<=m; i++){	
	cin>>a>>b;
	Union(a,b);
}

 

3. 최종적으로 같은 집합인지 확인

cin>>a>>b;
a=Find(a);
b=Find(b);
if(a==b) cout<<"Yes";
else cout<<"No";

 

 

그러면 이제 Union, Find 함수를 구현해보자.

void Union(int a, int b){
	a=Find(a);
	b=Find(b);
	if(a!=b) unf[a]=b;
}

int Find(int v){
	if(v==unf[v]) return v;
	else return Find(unf[v]);
}

 

Find함수는 학생의 집합 번호를 return한다. 

첫번 째 입력 1 2 의 경우

서로 집합이 다르므로 unf[1]=2

두번 째, 세번 째 입력 2 3  3 4를 하면 마찬가지로

 

이제 1 5를 입력 받으면 Find(1)을 하게 된다. 

Find(unf[1]) 즉 Find(2)가 호출된다.

Find(2)도 마찬가지로 Find(3)을 return받는다.

그런식으로 계속하고  Find(4)를 하면 v==unf[v]이므로 4를 return하고

최종적으로 Find(1)은 4를 return한다.

그리고 Find(1)은 4이고 Find(5)는 5이므로

unf[4]=5로 트리를 수정한다.

마찬가지로 Find(2) Find(3)을 하면 4로 나온다.

집합 번호는 root node의 번호이다.

 

정리

• Find와 Union함수를 이용해서 트리화 시킨다.
• 인덱스와 배열값이 같아야 종착점이다.

 

근데 이렇게 하면 굉장히 비효율적이다.

Find(1)을 하면 재귀가 계속 돌게 된다.

트리를 한가닥인 선형구조로 구현하는 것은 굉장히 비효율 적이다.

 

그래서 Find(1)을 호출하는 순간 바로 5번 호출하게 레벨 1짜리로 만드는 것이 좋다.

경로를 압축

 

Find 함수를 아래처럼 바꿔주면 된다.

int Find(int v){
	if(v==unf[v]) return v;
	else return unf[v]=Find(unf[v]);
}

Find 함수에서 return받은 값을 unf[v]에 저장(메모이제이션)하며 return 한다.

다시 처음부터 

1 2

2 3

3 4 

입력받으면

그리고 1 5 를 입력받으면 find(1)을 한다.

unf[1] = find(2)하고 find(2)를 return 받는다.

find(2)는 unf[2]=find(3)하고 find(3)을 return 받는다.

그렇게 쭉 unf[3]=find(4)까지 한다. 

그리고 재귀를 return 할때 배열에다 4를 넣으면서 return된다.

즉 unf[1] unf[2] unf[3]에 모두 4가 채워진다.

 

그리고 4번 노드에 5번을 넣으면

경로가 압축 되었다.

 

한 집합이면 전부 통일되어 있어야 하는 것은 아니다. (깔끔한 레벨 1짜리 트리로 만들어지지 않는다.)

모든 노드가 일자로 연결되는 것을 방지해준다는 의의가 있다.

 

※ 만약 그룹의 크기(노드 개수)를 관리하려면?

size라는 별도의 리스트를 하나 더 만들어서 관리하는 것이 가장 일반적

• 초기화: 처음에는 모든 노드가 자기 자신만 포함하므로 size를 모두 1로 초기화
• Union 연산 시: 두 그룹을 합칠 때, 부모가 되는 쪽의 size에 자식이 되는 쪽의 size를 더해준다.

size = [1] * (n + 1)

def union(a, b):
    rootA = find(a)
    rootB = find(b)
    
    if rootA != rootB:
        # rootA를 rootB 밑으로 합친다고 가정 
        s[rootA] = rootB
        
        # [핵심] rootB가 새로운 대장이 되었으니, rootA네 식구 수를 더해줌
        size[rootB] += size[rootA]

 

그리고 find(x)를 통해 루트 노드를 찾은 뒤 size를 조회

 

 

 

 

출처: it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++)