[UnionFind] Union Find의 개요

Union Find란?

Union Find는 상호 배타적 집합(disjoint set)을 표현할 때 쓰는 자료구조입니다.
라고 설명을 하면 무슨 소리인지 잘 모를 수도 있겠죠.

아주 간단하게 설명하자면, 전체 집합을 공통원소가 없는 부분 집합들로 나눠서 저장하는 자료구조입니다.

Union Find의 연산

Union Find는 세 가지 연산을 지원합니다.

  1. init : 모든 원소가 모두 서로 다른 집합에 속하게 초기화합니다.
  2. Union : 두 원소를 한 집합으로 묶어줍니다.
  3. Find : 특정 원소가 어떤 집합에 속하는 지 알려줍니다.

a와 b가 같은 집합이라면 Union(a, b)를 이용해 서로 묶어주고, c와 d가 같은 집합에 있는지 판단하기 위해서는 Find(c) == Find(d)를 이용해 검사해주면 됩니다.

다음 글에서는 배열과 트리를 Naive한 구현을 알아보겠습니다.