Union-Find

🔰 개념

그래프에 사이클이 생성되는지 판별하는 알고리즘이다.

union 연산

여러 노드가 있을 때 특정 2개의 노드를 연결해 1개의 집합으로 묶는 연산이다.

노드 a, b가 각각 A, B 집합에 속 때, union(a, b) = A ∪ B 다.

find 연산

두 노드가 같은 집합에 속해 있는지를 확인하는 연산이다.

자신의 대표 노드를 찾아준다.

노드 a가 집합 A에 속할 때, find(a)는 A 집합의 대표 노드를 반환한다.

단순히 대표 노드를 찾는 역할만 하는 것이 아니라, 그래프를 정돈하고 시간 복잡도를 향상시킨다.

🔰원리

초기화: 일반적으로 대표 노드를 저장하는 1차원 배열을 이용한다. 처음에는 노드가 연결되어 있지 않으므로 각 노드가 모두 대표 노드다. 따라서 배열을 자신의 인덱스값으로 초기화한다.

union 과정: 2개의 노드를 선택해 union 연산을 수행한다. 하나를 대표 노드로 설정해 다른 노드의 대표 노드 값을 대체한다(배열의 값을 수정한다.) 예를 들어, union(1, 4)를 하고 4번 노드의 대표 노드를 1로 설정한다. 항상 대표 노드를 연결한다. 두 노드의 대표 노드가 같을 경우, 두 노드를 연결하면 사이클이 생긴다는 의미다.

find 과정: 선택한 노드가 대표 노드가 아닐 때, find 연산으로 배열에 저장된 값을 따라 대표 노드를 찾는다(배열에 저장된 값과 인덱스-현재 노드가 일치하는지 확인한다.). 인덱스와 배열에 저장된 값이 일치하면 해당 노드가 대표 노드다. 대표 노드를 찾을 때까지 반복한다. -> 재귀 함수로 구현한다. 대표 노드에 도달하면 재귀 함수를 빠져나오면서 거치는 모든 노드값을 찾은 대표 노드값으로 변경한다.

결과: 결과적으로, 모든 노드가 루트 노드(유일한 대표 노드)에 직접 연결되는 형태로 변경된다. 이러한 형태로 변경되면 이후 find 연산이 진행될 때 경로 압축의 효과가 나타난다.