[자료구조] 디스조인트-셋(Disjoint-Set) - 유니온 파인드

해당 글은 마이구미님의 글과 위키백과를 참고하며 스스로 공부한 내용을 정리한 것입니다.

Disjoint-Set을 같이 공부해봅시다!

Disjoint(서로소) Set(집합)는 많은 서로소 부분집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료구조입니다.

이러한 특징으로 인해 Disjoint Set은 파티션(partitioning) 문제에 주로 이용됩니다. 

Disjoint Set 자료구조에는 3가지의 중요한 연산이 존재합니다.

서로소 집합이란? 공통 원소가 없는 두 집합, 교집합이 공집합인 집합입니다.

---

연산

1. 메이크 셋 (MakeSet): 말 그대로 특정 한 원소만을 가지는 집합(들)을 만드는 것입니다.

2. 파인드 (Find): 어떤 원소가 주어졌을 때 이 원소가 속한 집합을 반환 합니다. 일반적으로 해당 원소가 속한 집합을 대표하는 원소를 반환 합니다.

3. 유니온 (Union): 두 개의 집합을 하나의 집합으로 합치는 연산입니다. 이 방법에서 유니온 연산은 두 대표 원소를 입력 인자로 사용합니다.

※ 대표 원소: 사용되는 연산들을 보면 특정 원소가 속한 집합을 대표하는 대표 원소가 쓰입니다. 그러니 문제를 해결하기 전에 대표를 정할 기준을 정해야 합니다. (숫자면 가장 작은 수, 문자면 사전순 가장 앞의 단어 등)

---

구현

디스조인트 셋 자료구조는 일반적으로 트리 구조로 구현됩니다. 하나의 집합은 하나의 트리로 구현되며 트리의 루트노드가 해당 집합의 대표원소가 되는 것입니다. 이때 경로 압축(path compression)이라는 방법을 사용하여 연산 속도를 향상시켜 특정 원소에서 해당 원소가 속한 집합의 대표원소에 바로 접근 할 수 있게합니다.

경로압축(path compression)은 파인드 연산을 수행 할 때마다 루트 노드까지 순회중 방문한 각 노드들이 직접 루트 노드를 가리키도록 갱신합니다. 순회는 재귀 함수를 통해 진행됩니다.

※ 배열 parents : parents[x] = y; 라는 문장에서 특정 원소 x가 속한 집합의 대표 원소가 y라는 것을 의미합니다.

메이크 셋 연산 (MakeSet)

void make_set(int x){
	parents[x] = x;    // 자기 자신만을 원소로 가지는 집합을 생성
	return;
}

파인드 연산 (Find)

int do_find(int x) {

	if(x == parents[x]) return x;   //해당 집합의 대표 원소가 자기 자신일 경우
   
	return parents[x] = do_find(parents[x]); //경로 압축: 순회하며 거처간 원소들을 바로 루트로 연결
    
}

유니온 연산 (Union)      

void do_union(int u,int v){

	u = do_find(u);   //원소 u가 속한 집합의 루트 노드-> u에 다시 대입.
	v = do_find(v);   //원소 v가 속한 집합의 루트 노드-> v에 다시 대입.
    
	if(u == v) return; // 루트노드가 같다면 이미 같은 집합이라는 의미 이므로 리턴
    
    	parents[u] = v; // 그렇지 않다면 v의 루트노드에 u의 루트 노드를 붙힌다.
    
	return;
}

---

연습

같이 문제를 풀면서 Disjoint-Set와 더 가까워져봅시다! 

[BOJ 1976번: 여행가자] https://www.acmicpc.net/problem/1976

#include<bits/stdc++.h>
using namespace std;
const int MAX=200+2;

bool impossible=false;
int N,M,parents[MAX]; // parents[x]=y 원소 x가 속한 집합의 대표 원소는 y임을 의미
vector<int> plan;

int do_find(int u){
	if(u==parents[u]) return u;
	return parents[u]=do_find(parents[u]); 
}

void do_union(int u,int v){  
	u=do_find(u);
	v=do_find(v);
	if(u==v) return;
	parents[u] = v;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin>>N>>M;
   
	for(int i=1;i<=N;i++) parents[i]=i; //MakeSet 연산을 for문으로 대신
    
	for(int i=1;i<=N;i++){
		for(int j=1;j<=N;j++){
			int connection;
			cin>>connection; 
			if(connection){  
				do_union(min(i,j),max(i,j));
                
                //연결 되어있을 경우 Union 연산, 큰 수가 루트노드가 되게 기준 설정 
			}
		}
	}

	while(M--){
		int city;
		cin>>city;
		plan.push_back(city);
	}
    
	//여행 계획 중 현재 도시와 다음 도시가 같은 집합인지 확인
   	 //( 대표 원소가 같다 == 같은 집합이다 == 연결되어있다 )
     
	for(int i=0;i<(int)plan.size()-1;i++){
		if(do_find(plan[i])!=do_find(plan[i+1])) impossible=true;
	}

	if(impossible) cout<<"NO\n";
	else cout<<"YES\n";

	return 0;
}

부족한 부분이 있으면 댓글 부탁드리겠습니다!