유니온 파인드 알고리즘

유니온 파인드 (Union-Find) ?

• 유니온 파인드(Union-Find)는 그래프의 연결성을 판별하기 위한 효율적인 자료구조이다. → 이를 통해 서로소 집합(Disjoint Set)을 관리하며, 다음과 같은 두 가지 주요 연산을 제공한다.

  • Union: 두 집합을 합친다.
  • Find: 특정 원소가 속한 집합(대표 원소)을 찾는다.

• 여러 노드가 존재할 때, 선택한 두 노드가 서로 같은 그래프에 속하는지 판별하기 위해 사용한다.

💡 유니온 파인드 핵심 개념 - 루트(대표원소)

• 각 집합은 고유한 루트 노드를 갖고 있으며, 모든 원소는 해당 루트를 참조한다.
• 두 원소가 같은 집합에 속하는지는 Find 연산으로 확인한다.

💡 유니온 파인드 - 구현

1. 초기화 : 유니온 파인드 자료구조를 위한 새로운 집합을 생성한다. → 각각의 노드가 자기 자신을 가리키도록 설정한다. ( = 처음에는 자기 자신이 트리의 최상위 노드이다. )

// 초기화: 각 노드는 자기 자신을 부모로 가짐
for (int i = 0; i < size; i++) {
		parent[i] = i;
}