유니온 파인드 트리(분리 집합)

소개

유니온 파인드 트리는 교집합이 없는 여러 집합들을 나타내는 자료구조입니다. 집합을 합치는 연산과 원소가 속해 있는 집합을 구하는 연산을 상수 시간에 처리할 수 있습니다. 

 

구조

유니온 파인드 트리는 여러 개의 트리가 모여 있는 구조입니다. 각각의 트리는 집합 하나를 나타내며, 트리의 루트 노드의 번호가 해당 집합을 대표합니다. 배열에서 각 노드의 부모 노드 번호를 저장하고 있으며, 배열에서 재귀함수를 통해 부모 노드를 타고 올라가 루트 노드를 찾는 방식으로 구현합니다. 

 

구현

i번 노드가 속해 있는 집합의 루트 노드를 구하는 find(i) 연산과 i, j번 노드가 속해 있는 두 집합을 합치는 union(i, j) 연산을 구현해야 합니다. 

find 연산

int par[100005];
int find(int i){
    if (par[i] == 0)
        return i;
    return find(par[i]);
}

par 배열에 부모 노드가 저장됩니다. 부모 노드가 없다면 0이 저장되어 있습니다. 

find() 함수는 입력받은 노드의 부모가 없다면 현재 노드의 번호를 반환하며, 아니라면 부모 노드로 한 칸 올라가는 단순한 재귀함수입니다. 

 

union 연산

void merge(int i, int j){
    i = find(i);
    j = find(j);
    if (i != j)
       par[i] = j;
}

입력받은 두 노드가 속한 집합의 루트 노드를 먼저 구한 뒤, 둘이 같은 집합에 속해 있지 않았다면 i가 속한 집합의 루트 노드의 부모를 j가 속한 집합의 루트 노드로 설정합니다. 이렇게 한다면 두 개의 트리가 하나로 합쳐지며 두 집합을 합칠 수 있습니다. 

 

최적화

위와 같은 식으로 코드를 작성한다면 union 연산을 수행할수록 트리의 깊이가 깊어지고, find연산도 느려질 것입니다. 이 문제를 해결하려면 가능한 모든 노드들이 루트 노드의 자식이 되어 트리의 깊이를 얕게 유지시켜야 합니다. 

int find(int i){
    if (par[i] == 0)
        return i;
    return par[i] = find(par[i]);
}

find함수를 위와 같이 조금 변경하면 find함수를 한 번 수행할 때마다 방문하는 모든 정점의 부모 노드가 루트 노드로 변경됩니다. 이렇게 최적화하면 트리의 깊이가 일정 수준 이상으로 깊어지지 않아 상수 시간에 연산을 처리할 수 있게 됩니다. 

 

활용

데이터를 여러 그룹으로 나누고 그룹들을 합쳐가는 작업이 필요할 때 사용됩니다. 

트리의 간선을 끊는 쿼리를 수행해야 할 때도 대부분 오프라인 쿼리와 유니온 파인드 트리를 이용하여 처리합니다. 

BOJ의 분리 집합 문제들이나 Union-find 문제 풀이 글들을 참고하시면 좋을 것 같습니다.