[6기 강남 조유석] Union-Find

안녕하세요. 강남멤버십 23-1기 조유석입니다.

이번 포스팅에서는 상호 배타적 집합(disjoint set)을 표현할 때 쓰는 Union-Find라는 독특한 형태의 자료구조를 알아보겠습니다.

Union-Find

Union-Find 트리는 공통 원소가 없는, 다시 말해 상호 배타적인 부분 집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료구조 입니다. Union-Find 트리는 주어진 원소들이 서로 같은 그룹에 속해 있는지가 중요합니다. 다음 그림과 같이 하나의 그룹은 하나의 트리이며, 어떤 노드가 어떤 노드의 부모인가 등이 중요한 것이 아니라 연결성을 중요시 합니다.

Union-Find 트리는 초기화, 합치기(Union), 찾기(Find) 이 세 가지 연산을 지원하며, 이 때 합치기(Union), 찾기(Find)의 두 연산을 지원한다고 해서 이 자료구조를 Union-Find 라고 부릅니다.

초기화

n개의 원소가 각각의 집합에 포함되어 있도록 초기화합니다.

Union

두 원소가 주어질 때 이들이 속한 두 집합을 하나로 합칩니다. 다음 그림과 같이 한 트리의 루트(그림에서 1)로부터 다른 트리의 루트(그림에서 5)에 선을 연결하면 2개의 트리가 1개의 트리가 되어 1개의 그룹이 됩니다.

Find

어떤 원소가 속한 집합을 반환합니다. 같은 그룹에 속해 있는지를 판정하는데는 그 요소가 포함되어 있는 트리의 루트를 조사합니다. 같은 루트라면 같은 그룹이라는 것을 알 수 있습니다. 다음 그림에서 6과 7은 모두 5에 도달하기 때문에 같은 그룹에 속해있음을 알 수 있습니다. 또한 2와 3은 모두 1에 도달하기 때문에 6이나 7과는 다른 그룹에 속해있음을 알 수 있습니다.

Union-Find 최적화

Union-Find 트리의 표현을 이용하면 Union 연산을 할 때 집합에 포함되는 모든 원소를 변경하는 대신 루트 하나의 정보만 바꾸면 됩니다. 하지만 트리를 사용하므로 연산의 순서에 따라 잘못하면 트리가 편향되는 문제를 피해갈 수는 없습니다. 이렇게 되면 Union 연산도, Find 연산도 으로 계산량이 엉망이 됩니다. 이와 같은 문제를 해결하는 방법 중 랭크에 의한 합치기(union-by-rank)와 경로 압축(path compression)에 대해 알아보겠습니다.

union-by-rank

- 각 트리에 대해 트리의 높이(rank)를 기억해 둔다.

- Union 시 2개의 트리의 rank가 다르면 rank가 작은 쪽에서 큰 쪽으로 Union 한다.

이 최적화를 이용하면 높이가 h인 트리가 생기기 위해서는 높이가 h-1개인 두 개의 트리가 합쳐져야 합니다. 트리의 높이가 h-1이기 위해 최소 x개의 노드가 필요하다면, 높이가 h가 되기 위해서는 최소 2x개의 노드가 필요합니다. 따라서 트리의 높이는 노드의 수의 로그에 비례하며, Union 연산, Find 연산의 시간복잡도는 이 아니라 이 됩니다.

path compression

Find를 실행한 노드에서 거쳐간 모든 노드를 루트에 연결합니다. 이후부터는 이 노드들에 대해서는 바로 루트를 알 수 있습니다.

두 가지 최적화를 모두 적용한 Union-Find의 수행 시간은 으로 알려져 있습니다. 이것은 보다 고속으로 동작하며, 현실적인 모든 입력에 대해 상수시간에 동작한다고 봐도 좋습니다.

Union-Find 구현

Union-Find로 문제를 해결하는 대표적 사례로는 Kruskal의 Minimum Spanning Tree 알고리즘이 있으며, 이 외에도 Union-Find에 다른 정보를 추가함으로써 해결할 수 있는 문제들이 많습니다.

이상으로 Union-Find 에 대해 알아보았습니다.

감사합니다.

Reference

  - ‘프로그래밍 대회에서 배우는 알고리즘 문제해결 전략’ - 구종만 저

  - ‘프로그래밍 콘테스트 챌린징’ - Takuya Akiba, Yoichi Iwata, Masatoshi Kitagawa 저