[Union-Find] 유니온-파인드, 분리 집합 (백준 1717 - 집합의 표현 해설)

 

가장 기본적인 분리 집합(Disjoint Set)을 구현하면 풀 수 있는 문제를 통해 유니온-파인드(Union-Find) 자료구조 살펴보자.

 

문제

www.acmicpc.net/problem/1717

1717번: 집합의 표현

 

 

풀이

 

solved.ac 난이도: Gold 4

 

가장 기본적인 분리 집합(Disjoint Set)을 구현하면 풀 수 있는 문제.

분리 집합은 유니온-파인드(Union-Find) 자료구조를 사용하여 구현할 수 있다.

유니온-파인드는 말 그대로 두 가지 기능을 하는 자료구조이다.

 

Union: 두 노드가 속한 집합(트리)를 합친다.

Find: 노드가 속한 집합을 찾는다.

 

 

유니온-파인드의 각 집합(트리)의 표현은 자신의 부모를 저장하는 parent[]배열로 간단히 구현한다.

루트는 부모 노드가 없으므로 자기 자신을 저장해주자.

따라서 분리 집합을 구현하는 클래스 class DisjointSet의 생성자에서 parent[idx] = idx로 먼저 처리를 해주자.

 

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

 

 

이제 노드가 속한 집합을 찾는 Find함수를 구현하자.

 

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

Find함수는 u의 부모 노드로 재귀 호출하여 최종적으로 집합의 루트(자신이 부모)에 도달할 때까지 진행하면 된다.

추가적인 최적화가 존재하지만 일단 Union함수를 살펴보자.

 

 

void Union(int u, int v){
  u = Find(u); v = Find(v);
 
  if(u == v)
    return;
 
  parent[u] = v;
  return;
}

u가 속하는 집합과 v가 속하는 집합을 합치기 위해 일단 u와 v 집합의 루트를 Find해주자.

만약 찾은 루트 값, u와  v가 같다면 서로 같은 집합에 속한다.

 

다르다면 v를 u의 부모를 저장해 주어 v의 하위 노드로 만든다.

 

 

Find의 최적화

이러한 구현은 굉장히 간단하지만 Union과정에서 주어지는 v의 하위에 u를 합치다 보면

한쪽에 노들이 몰려있는 편향 트리(Skewed Tree)가 생길 수 있다.

이러한 트리에서 리프 노드에서 Find를 하게 되면 root까지 도달하는데 트리의 높이만큼의 복잡도가 필요하다.

따라서 Find함수를 아래와 같이 변경해주자.

 

 

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

 

parent[u] = Find(parent[u]) 를 통해 재귀 호출하여 찾은 root의 값을 모든 노드의 parent로 저장해준다.

이렇게 하면 한 단계씩 부모 노드로 올라가지 않아도 바로 root노드로 접근이 가능하다.

이러한 최적화를 경로 압축(path compression)이라고 한다.

 

 

Union의 최적화 (union-by-rank)

기본적인 구현의 가장 큰 문제는 편향 트리를 막을 수 없다는 것이다.

하지만 항상 높이(rank)가 작은 트리를 높이가 큰 트리에 넣는다면 트리의 높이가 커지는 것을 막을 수 있다.

이를 랭크에 의한 합치기(union-by-rank)라고 한다.

합쳐진 트리의 높이가 높아지는 경우는 오직 두 트리의 높이가 같은 경우로 합쳐진 트리의 높이(rank)는 1만 증가한다.

(항상 트리의 루트의 바로 하위 노드로 합쳐지기 때문)

 

이를 구현한 코드는 다음과 같다.

 

 

void Union(int u, int v){
  u = Find(u); v = Find(v);
 
  if(u == v)
    return;
    
  if(rank[v] < rank[u]) //rank는 항상 v가 크도록
    swap(u,v);
 
  parent[u] = v;  //u를 v의 하위 노드로
  if(rank[v] == rank[u])
    ++rank[v];
    
  return;
}

 

 

 

단, 해당 문제에서는 iostream의 입출력 함수는 시간 초과를 발생시키므로 cstdio의 입출력 함수를 사용해주자.

 

참조 서적: 알고리즘 문제 해결 전략(백종만 저)

 

코드