유니온 파인드 구조

1. 상호 배타적 집합(Disjoint Set)과 유니온 파인드(Union-Find) 구조

유니온 파인드 구조를 보기에 앞서 상호 배타적 집합에 대해 집고 넘어가겠다. 상호 배타적 집합이란 각 집합들이 서로 공통원소를 가지지 않는 집합들을 말한다. 상호 배타적 집합의 원소의 정보를 저장하고 조작하는 자료 구조가 유니온-파인드 자료 구조이다. 이따 언급될 union 함수와 find 함수를 지원한다고 해서 유니온-파인드 자료 구조라고 부른다.

2. 유니온 파인드 구조를 위한 세 가지 함수

1. 초기화 : n개의 원소가 각각의 집합에 포함되도록 초기화한다.
2. 찾기(find) 연산: 특정 원소 a 가 주어졌을 때 해당 원소가 속한 집합의 루트를 반환하는 연산이다.(트리와 루트는 일대일 대응 때문에 찾은 루트가 원소가 속한 집합을 대표한다.)
3. 합치기(Union) 연산: 두 원소 a,b가 주어졌을 때 각각이 속하는 집합을 서로 합치는 연산이다.

3. 관련 코드

3.1 초기화 함수

각 원소의 루트를 자기 자신으로 초기화 한다.

DisjointSet(int n): parent(n){
    	for(int i=0;i<n;i++)
        	parent[i]=i;
}

3.2 Find 함수

parent[u] 는 u의 부모노드가 아닌 루트 노드를 저장함으로써 find(u)가 호출 되었을 때 바로 루트를 반환한다. 이를 '경로 압축 최적화' 라고 부른다.

int find(int u){
   	if(u==parent[u])
    	   return u;
        return parent[u]=find(parent[u]);
   }

3.3 Union 함수

두 원소 u, v 가 주어졌을 때 find함수를 통해 두 원소가 속한 집합의 루트를 찾는다. 두 값이 같다면 같은 집합에 속한 것이므로 함수를 종료한다. 두 값이 다르다면 루트의 값이 작은 집합에 다른 집합을 포함 시킨다.

void union(int u,int v){
   	u=find(u);v=find(v);
    	if(u==v)
    		return;
        if(u>v)
        	swap(u,v) 
        parent[v]=u;
   }

4. 유니온-파인드 구조 전체 코드

struct DisjointSet{
	vector<int> parent;
    
    //1. parent 초기화
    DisjointSet(int n): parent(n){
    	for(int i=0;i<n;i++)
        	parent[i]=i;
   }
   // 2. 루트 노드를 찾는 함수. 이때 경로 압축 기법을 사용한다.
   int find(int u){
   	if(u==parent[u])
    	   return u;
        return parent[u]=find(parent[u]);
   }
   
   // 3. 두 트리를 합치는 함수. rank를 활용한 개선된 방법도 있으나 기본적인 방법을 사용하겠음.
   void union(int u,int v){
   	u=find(u);v=find(v);
    	if(u==v)
    		return;
        if(u>v)
        	swap(u,v) // 두 트리 중 루트의 숫자가 작은 것이 합친 트리의 루트가 될 수 있게끔 하기 위함.
        parent[v]=u;
   }
};    

5. 언제 사용되는가?

그래프 유형에서 사이클의 존재를 확인할 때 사용된다
대표적으로 MST 알고리즘 중 크루스칼 알고리즘에서 트리를 확장 시 사이클이 발생하는지 확인할 때 유니온 파인드 구조를 사용한다

6. 시간 복잡도

find함수는 호출할 때 마다 수행 시간이 바뀌기 때문에 분할 상환 분석(?)도 이용해야 하며 각 수행에 걸리는 평균시간은 O(a(n)) 이라 한다. a(n) 은 앵커만 상수 라 불리는 함수인데 모든 크기 n 에 대해 4이하의 값이라 한다. 즉 상수시간이 걸린다.

결론 : O(1) 의 시간 복잡도를 가짐

참고 자료

알고리즘 문제 해결 전략 (종만북)