유니온 파인드

유니온 파인드란?

유니온 파인드는 그래프 자료구조에서도 사용하는 알고리즘으로 일반적으로 여러 노드가 있을 때 특정 2개의 노드를 연결해 1개의 집합으로 묶는 Union 연산과 두 노드가 같은 집합에 속해 있는지를 확인하는 Find 연산으로 구성되어 있는 알고리즘이다.

union, find 연산

• union 연산: 각 노드가 속한 집합을 1개로 합치는 연산
• find 연산: 특정 노드 a에 관해 a가 속한 집합의 대표 노드를 반환하는 연산

유니온 파인드의 원리 이해

1. 초기화

유니온 파인드를 표현하는 일반적인 방법은 1차원 배열을 이용하는 것이다.
처음에는 노드가 연결되어 있지 않으므로 각 노드가 대표 노드가 된다.
각 노드가 모두 대표 노드이므로 배열은 자신의 인덱스 값으로 초기화한다.

하먄 박스 -> 인덱스, 회색 박스 -> 값

2. union 연산 수행

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

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

union(4,6) 연산을 하면 4, 6은 대표 노드가 아니다. 그래서 각 노드의 대표 노드를 찾아 올라간 다음 그 대표 노드를 연결한다. 지금의 경우 4의 대표 노드 1에 6의 대표 노드 5를 연결한 것이다. 그러면 배열은[1, 2, 3, 1, 1, 5]가 된다.

3. find 연산 수행

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

find 연산의 작동 원리

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

find 연산은 시간 복잡도가 줄어드는 효과를 얻을 수 있다. 연산을 할 때 거치는 노드들이 대표 노드와 바로 연결되는 형태로 변경되어 추후 노드와 관련된 find 연산 속도가 O(1)로 변경된다.

상기 사진과 같은 형태로 변경되면 이후 find 연산에서는 한 번의 이동으로 바로 대표 노드를 찾을 수 있다.