union-find(유니온 파인드)

• 여러 노드가 있을 때 특정 2개의 노드를 연결해 1개의 집합으로 묶는 union 연산과
• 두 노드가 같은 집하에 속해 있는지를 확인하는 find 연산으로 구성된 알고리즘입니다.

union 연산

• 각 노드가 속한 집합을 1개로 합치는 연산으로
• 노드 a, b가 $a \in A, b \in B$ 일 때 union(a, b)는 $A \cup B$를 의미합니다.

find 연산

• 특정 노드 a에 관해 a가 속한 집합의 대표 노드를 반환하는 연산입니다. 노드 a가 $a \in A$ 일 때 find(a)는 A 집합의 대표 노드를 반환합니다.

union-find 원리 이해하기

1. union-find를 표현하는 일반적인 방법은 1차원 배열을 이용하는 것입니다.
   • 처음에는 노드가 연결되어 있지 않으므로 각 노드가 대표노드가 됩니다.
   • 각 노드가 모두 대표 노드이기 때문에 배열은 자신의 인덱스값으로 초기화합니다

2. union(a, b)
   • a와 b의 대표노드를 찾아 a 노드에 연결합니다.
   • 이 때 b 노드의 value를 a 노드의 value로 업데이트 합니다.

3. a와 b가 대표노드가 아닐경우 각 노드의 대표노드를 찾아 연결합니다
   • 4의 대표노드는 1이고 6의 대표노드는 5이므로 union(1, 5)를 수행합니다

3. find 연산은 자신이 속한 집합의 대표 노드를 찾는 연산입니다.
   • 단순히 대표 노드를 찾는 것뿐만 아니라 그래프를 정돈하고 시간 복잡도를 줄이는 효과가 있습니다.

find 연산의 작동 원리

1. 대상 노드 배열에 index 값과 value 값이 동일한지 확인
2. 동일하지 않으면 index[value]로 이동
3. index 와 value가 같을 때까지 1~2번을 반복
4. 대표 노드에 도달하면 재귀 함수를 빠져나오면서 거치는 모든 노드의 value를 대표 노드의 value로 업데이트