🔎 유니온 파인드란?
- 그래프 알고리즘으로서 두 노드가 같은 그래프에 속하는지 판단하는 알고리즘이다.
- 각 집합이 서로 공통 원소를 가지지 않는 서로소 집합 혹은 상호 베타적 집합이 구해진다.
- 합집합 찾기라는 의미를 가진다.
- 크게 3가지의 과정을 거치게 된다.
- Initialization(초기화) : 각 노드가 각각의 집합에 포함되도록 초기화하는 과정
- Find(찾기) : 특정 노드의 부모를 찾는다. (해당 노드가 속한 집합의 루트를 반환한다.)
- Union(합치기) : 두 노드 A와 B를 한쪽으로 합친다. (노드 번호가 작은 쪽 or 큰 쪽 or 트리 높이가 낮은 쪽)
📌 구현
(1) Initialization(초기화)
자기 자신만을 집합의 원소를 가질 수 있도록
모든 값이 자기 자신을 가리키도록 배열을 만드는 과정이다.
여기서 배열의 크기를 N+1로 하고 0번째 인덱스를 사용하지 않아도 무방하다.
위 과정을 소스코드로 보면 아래와 같다.
const init = (N) => {
return Array(N).fill(0).map((value, idx) => idx);
};
console.log(init(8));
// 결과값 : [ 0, 1, 2, 3, 4, 5, 6, 7 ](2) Find(찾기)
초기화가 완료되었다면 위 그림처럼 배열이 생성되었을 것이다.
위 배열 중에서 1번과 2번을, 4번부터 6번까지를 합쳐주고 싶은데, 어떻게하면 좋을까?
합치는 방법은 2번 노드의 배열 값을 1번 노드의 배열 값으로 바꿔주면 된다.
그림으로 표현하자면 아래와 같다.
2번 노드의 배열 값을 연결하고자 하는 노드인 1번 노드의 배열 값으로 바꿔줌으로써
1번과 2번이 연결이 되었다고 판단한다.
위와 마찬가지로 4번부터 6번까지 연결하고 싶다면 아래와 같은 순서로 진행이 될 것이다.
- 6번과 5번 배열을 연결
- 6번 노드의 배열 값을 5번 노드의 배열 값으로 바꿔준다.
- 5번과 6번 배열을 연결
- 5번 노드의 배열 값을 4번 노드의 배열 값으로 바꿔준다.
그렇다면 어떻게 본인과 연결된 노드들을 알 수 있을까?
N번 노드의 부모를 찾는 과정은 다음과 같다.
- N번째 배열의 저장된 값을 확인한다.
- N번째 배열의 저장된 값을 인덱스 값으로 가지는 M번째 배열의 저장된 값을 확인한다.
- 두 개가 일치한다면 두 개는 연결되어있으며 N 노드의 부모는 M노드가 되는 것이다.
이해를 돕기 위해 구체적인 예시로 6번 노드의 부모를 찾아가는 과정을 서술해보도록 하겠다.
- 배열의 6번째 노드가 가지는 값을 확인한다. => 5
- 배열의 5번째 노드가 가지는 값을 확인한다. => 4
- 배열의 4번째 노드가 가지는 값을 확인한다. => 4
배열의 인덱스와 값이 일치한다. => 4번 노드가 6번 노드가 속해있는 트리의 루트 노드이다.
소스코드로 보면 아래와 같다.
const find = (x) => {
// 배열의 인덱스와 배열의 값이 일치한다면 루트노드의 인덱스 값을 리턴한다.
if (parent[x] === x) {
return x;
} else {
// 일치하지 않는다면 재귀함수를 통해 1 depth 더 들어가도록 한다.
return find(parent[x]);
}
};위의 방법대로 유니온 파인드를 구현한다면 편향 트리로 구현이 되어지기 때문에
시간복잡도가 O(N)이 걸리게 된다.
이렇게 편중되어있다면 탐색하는데 당연히 시간이 오래 걸릴 수 밖에 없을 것이다.
이러한 문제를 경로 압축을 통해서 어느정도 해소할 수 있게 된다.
그림으로 본다면 아래와 같이 표현할 수 있을 것이다.
📌 경로 압축(Path compression)이란 ?
모든 노드는 루트 노드 밑에 속해있기 때문에 부모 노드를 찾았다면
해당 노드에 기록된 값들을 모두 부모 노드의 값으로 바꿔준다면 시간복잡도를 개선할 수 있다.
경로를 합쳐주는 Union 연산을 진행할 때 경로 압축을 해줄 수 있다.
경로 압축이 완료되었다면 아래와 같을 것이다.
소스는 아래와 같다.
const find = (x) => {
// 배열의 값과 인덱스가 같다면 부모 노드의 인덱스를 반환한다.
if (parent[x] === x) {
return x;
}
// 경로 압축을 위해 부모노드의 값으로 바꿔준다.
const currentParent = find(parent[x]);
parent[x] = currentParent;
return currentParent;
};(3) Union(합치기)
두 노드가 포함된 집합을 합치는 과정으로서 부모 노드로 올라갈 수록 번호가 작다는 가정 하에,
두 집합을 합칠 때 번호가 작은 노드 아래에 번호가 큰 노드가 들어갈 수 있도록 한다.
Union 과정이 완료된다면 아래와 같을 것이다.
소스로 보면 아래와 같을 것이다.
const union = (A, B) => {
A = find(A);
B = find(B);
// A와 B가 같다면 이미 연결되어 있는 경우
if( A === B ) return;
// 배열의 B 인덱스에 A 값을 저장한다.
parent[B] = A;
};유니온 과정까지 마치게된다면 유니온 파인드 로직은 끝이난다.
최종 소스코드
여기까지의 과정을 소스코드로 한번에 나타내면 아래와 같다!
// 초기화
const init = (N) => {
return Array(N).fill(0).map((value, idx) => idx);
};
// x의 루트노드 찾는 함수
const find = (x) => {
// 배열의 값과 인덱스가 같다면 부모 노드의 인덱스를 반환한다.
if (parent[x] === x) {
return x;
}
// 경로 압축을 위해 부모노드의 값으로 바꿔준다.
const currentParent = find(parent[x]);
parent[x] = currentParent;
return currentParent;
};
// 두 노드를 합치기 위한 함수
const union = (x, y) => {
x = find(x);
y = find(y);
// x와 y가 같다면 이미 연결되어 있는 경우
if( x === y ) return;
// x와 y 둘 중 큰 값을 가지는 부모 인덱스를 작은 값을 가지는 변수로 넣는다.
if (x < y) parent[y] = x;
else parent[x] = y;
};
// 같은 부모를 가지는지 확인하는 함수
const isUnion = (x,y) => {
x = find(x);
y = find(y);
if(x === y) { return true; }
return false;
}참조한 사이트 : https://ip99202.github.io/posts/%EC%9C%A0%EB%8B%88%EC%98%A8-%ED%8C%8C%EC%9D%B8%EB%93%9C(Union-Find)/
