<aside> 💡 그래프 영역이라고는 볼 수 없는데, 실제로 그래프 문제에서 부분 알고리즘으로 많이 사용된다.

</aside>

유니온 파인드는 일반적으로 여러 노드가 있을 때 특정 2개의 노드를 연결해 1개의 집합으로 묶는 union 연산과 두 노드가 같은 집합에 속한지를 확인하는 find 연산으로 구성되어 있는 알고리즘이다.

※ find 연산 : 자신의 대표 노드를 찾아주는 연산이라고 보면 된다.

유니온 파인드의 핵심 이론

유니온 파인드는 union, find 연산을 완벽히 이해하는 것이 핵심이다.

<aside> 💡 union, find 연산

• union 연산 : 각 노드가 속한 집합을 1개로 합치는 연산이다.
  노드 a,b가 a ∈ A, b ∈ B일 때 union(a, b)는 A ∪ B를 말한다.
• find 연산 : 특정 노드 a에 관해 a가 속한 집합의 대표 노드를 반환하는 연산이다. 노드 a가 a ∈ A일 때 find(a)는 A 집합의 대표 노드를 반환한다. </aside>

유니온 파인드 원리 이해하기

<aside> 💡 find 연산의 작동 원리

1. 대상 노드 배열에 index값과 value값이 동일하지 확인한다.
2. 동일하지 않으면 value값이 가리키는 index 위치로 이동한다. (동일하면 대표노드)
3. 이동 위치의 index값과 value값이 같을 때까지 1~2를 반복한다. (재귀함수로 구현)
4. 대표 노드에 도달하면 재귀 함수를 빠져 나오면서 거치는 모든 노드값을 루트 노드로 변경한다. </aside>

[1717] 집합 표현하기

[1976] 여행 계획 짜기

[1043] 거짓말쟁이가 되긴 싫어