Union Find란?
Union Find는 상호 배타적 집합(disjoint set)을 표현할 때 쓰는 자료구조입니다.
라고 설명을 하면 무슨 소리인지 잘 모를 수도 있겠죠.
아주 간단하게 설명하자면, 전체 집합을 공통원소가 없는 부분 집합들로 나눠서 저장하는 자료구조입니다.
Union Find의 연산
Union Find는 세 가지 연산을 지원합니다.
- init : 모든 원소가 모두 서로 다른 집합에 속하게 초기화합니다.
- Union : 두 원소를 한 집합으로 묶어줍니다.
- Find : 특정 원소가 어떤 집합에 속하는 지 알려줍니다.
a와 b가 같은 집합이라면 Union(a, b)를 이용해 서로 묶어주고, c와 d가 같은 집합에 있는지 판단하기 위해서는 Find(c) == Find(d)를 이용해 검사해주면 됩니다.