👀 'Do it! 알고리즘 코딩테스트 with Python(김종관 저)'을 공부하고 정리한 내용입니다.

1. 개념

유니온 파이드는 그래프에서만 사용되는 알고리즘은 아닙니다.
집합에서 대표 노드를 찾는다거나, 각각의 원소를 유니온 해서 하나의 집합으로 만들거나 하는 식의 방법으로도 활용 가능합니다.

하지만 오늘은 그래프에서의 유니온 파인드는, 그래프의 사이클이 생성되는지 판별하는 역할을 해줍니다.

각 노드가 같은 집합에 속하는지 판별하기도 하며, 이 때문에 합집합 찾기 알고리즘이라고도 부르며, 역으로 서로 연결되어 있지 않은 노드를 판별할 수도 있기 때문에 서로소 집합 (Disjoint-set)이라고도 부릅니다.

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

union 연산

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

find 연산

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

2. 원리 이해하기

2-1.유니온 파인드를 표현하는 일반적인 방법은 1차원 배열을 이용하는 것입니다. 처음에는 노드가 연결되어있지 않으므로, 각 노드가 대표 노드가 됩니다.

각 노드가 모두 대표 노드이므로 배열은 자신의 인덱스 값으로 초기화합니다.

2-2. union 연산 수행

2개의 노드를 선택해 각각의 대표 노드를 찾아 연결하는 union 연산을 수행합니다.
배열을 보면 1, 4 와 5, 6을 union 연산으로 연결합니다.
배열[4]는 1로, 배열[6]은 5로 업데이트합니다.

이렇게 업데이트 하는 것의 의미를 이해해야 합니다. 1, 4의 연결을 예로 들자면, 1은 대표 노드, 4는 자식 노드로 union 연산을 하므로 배열[4]의 대표 노드를 1로 설정한 것입니다. 다시 말해 자식 노드로 들어가는 노드값 4를 대표 노드값 1로 변경한 것입니다. 그 결과 각각의 집합이었던 1, 4는 하나로 합쳐집니다.

union(5,6)은 6의 대표 노드를 5로 업데이트 합니다.

2-3. find 연산 수행

find 연산은 자신이 속한 집합의대표 노드를 찾는 연산입니다. find 연산은 단순히 대표 노드를 찾는 역할만 하는 것이 아니라 그래프를 정돈하고 시간 복잡도를 향상시킵니다.

find 연산의 작동 원리

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

!! 중요 !!
find 연산은 잘 생각하면 시간 복잡도가 줄어드는 효과를 얻게 됩니다.
연산을 할 때 거치는 노드들이 대표 노드와 바로 연결되는 형태로 변경 되는 것을 알 수 있습니다.
이렇게 되면 추후 노드와 관련된 find 연산속도가 O(1)로 변경됩니다.
아래는 예시입니다.