알고리즘 - 유니온 파인드

유니온 파인드(Union Find)

---

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

유니온 파인드는 노드가 어떤 경로에 있는지 보다 서로 연결되어 있는지를 확인하기 위한 알고리즘이다. (같은 집합인지 확인)

대표 노드 배열

대표 노드를 저장하는 배열을 초기화한다. 

최초에는 인덱스 값을 그대로 저장 배열에 넣어준다. 처음에 각 노드들이 연결되어 있지 않고 서로 독립적으로 세팅되기 때문에 자기 자신이 대표 노드가 된다.

union 연산

유니온 연산을 통해서 하나의 집합 즉, 노드간 연결을 해준다. (대표 노드를 비교하여 더 작은 값을 대표 노드로 설정한다.)

처음에 유니온 연산이 가능한 이유는 초기에는 대표 노드로 초기화 되기 때문이다.

find 연산

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

find 연산의 작동 원리

1. 대상 노드 배열에 index 값과 value 값이 동일한지 확인한다.

2. 동일하지 않으면 value 값이 가리키는 index 위치로 이동한다.

3. 이동 위치의 index 값과 value 값이 같을 때까지(대표 노드를 찾을 때까지) 1~2번을 반복한다.

4. 대표 노드에 도달하면 재귀 함수를 빠져 나오면서 거치는 모든 노드값을 루트 노드값으로 변경한다.

유니온 파인드 알고리즘을 사용하면 경로 압축이 중요한데 경로 압축을 통해 실제 그래프에서 여러 노드를 거쳐야 하는 경로에서 그래프를 변형해 더 짧은 경로로 갈 수 있도록 함으로써 시간 복잡도를 효과적으로 줄이는 방법을 말한다.