-Union Find 알고리즘이란?
서로소 집합 알고리즘과 같은 개념으로 여러 개의 노드가 존재하는 그래프에서 두 노드가 연결되어있는지 판별하는 알고리즘이다. 구현에 필요한 자료구조로는 1) 모든 정점들의 부모 정점을 표현하기 위한 배열이 필요하다.
다음과 같이 6개의 독립적인 노드가 존재한다고 할 때 배열을 이용해서 원소에 해당 노드의 부모 노드를 표시하게 된다.
현재는 모두 독립된 노드이기 때문에 자기 자신을 부모로 삼는다고 할 수 있다.
| 1 | 2 | 3 | 4 | 5 | 6 |
| 1 | 2 | 3 | 4 | 5 | 6 |
이와 같은 상태에서 만약 1번 정점과 2번 정점이 연결을 수행하게 되면 두 정점을 합치는 Union작업이 수행되게 되는데, 이 과정을 거치고 나면 아래와 같이 2번 정점의 원소를 부모 정점인 1로 바꿔주게 된다. 이 과정에서 중요한 점은 두 정점을 합치는 Union작업이 진행 될 때 두 정점의 부모 노드 중 작은 값을 큰 정점의 부모로 삼는다는 점이다. 즉, 아래의 경우에는 1번 정점의 부모는 1이고 2번 정점의 부모는 2였기 때문에 1 <2로 2번 정점의 부모가 1이 되는 것이다.
| 1 | 2 | 3 | 4 | 5 | 6 |
| 1 | 1 | 3 | 4 | 5 | 6 |
같은 방식으로 2번 정점과 3번 정점을 Union해주게 되면, 아래의 표와 같이 2 <3으로 3번 정점의 부모 노드가 2가 되는 것이다. 여기까지의 결과로 정점 1, 2, 3은 모두 연결되었으며 3번 정점의 부모 정점은 2번, 2번 정점의 부모 노드는 1번이 되는 것이다.
| 1 | 2 | 3 | 4 | 5 | 6 |
| 1 | 1 | 2 | 4 | 5 | 6 |
이와 같은 방법으로 정점 4, 5, 6도 모두 연결 해준다면 최종적으로 아래와 같은 배열이 완성될 것이다. 이 배열이 의미하는 바는 두 개의 그래프 부분집합이 생성되게 된다는 것인데, 이제 이러한 그래프들의 정점간의 연결 여부를 찾아내는 작업이 Find작업이 되는 것이다. Find작업의 핵심은 연결 여부를 확인하고자 하는 두 정점의 부모 노드를 확인하여 일치하면 두 정점은 연결되어 있는 것이고, 일치하지 않으면 연결되어 있지 않은 것이다. 아래와 같은 경우 2번 정점과 5번 정점이 연결되어 있는지 여부를 Find(2,5)로 확인해보면, 정점 2의 부모 정점은 1이 될 것이고, 5의 부모 정점은 4가 되므로 일치하지 않아 연결되지 않는다는 사실을 알 수 있다.
| 1 | 2 | 3 | 4 | 5 | 6 |
| 1 | 1 | 2 | 4 | 4 | 5 |
자세한 내용은 코드를 보며 이해해보자.
public class Union_Find {
public static int getParent(int[] arr,int x) { // 특정 정점의 부모 정점을 찾는 메소드로 재귀호출을 반복한다.
////////////////////////////////////////////////////////////////
//만일, 최종의 배열 상태에서 3번 정점의 부모노드를 찾는다고 가정한다면,
//3번 인덱스의 값은 2이므로 메소드는 진행되며, 3번 정점의 부모 정점인 2번 정점의 부모를 확인하기
//위해 재귀호출을 수행한다. 2번 정점이 전달되면, 2번 인덱스의 값은 1이므로 위를 다시 반복,
//결국 1번 인덱스의 값 = 1 이므로 부모 정점을 재귀호출의 종료로써 반환하여
//결과적으로 3번 정점의 부모 정점은 1번 정점이 된다는 것을 알 수 있다.
////////////////////////////////////////////////////////////////
if(arr[x] == x) return x; // 자기 자신이 부모일 경우
return arr[x] = getParent(arr,arr[x]);
}
public static void unionParent(int[] arr,int a,int b) { // 글에서 언급한 Union연산
// 위의 부모 정점을 찾기 위한 메소드를 호출 해 각 정점의 부모 정점을 찾아낸 후,
// 두 부모 정점 중 작은 값을 큰 값의 부모노드로 저장해준다.
// 예를 들어 최종의 배열 상태에서 2번 정점과 4번 정점을 연결한다 하면, 각각의 부모 정점은
// 1과 4이므로 4번 정점의 부모노드를 1번 정점으로 하여 연결하게 된다.
a = getParent(arr,a);
b = getParent(arr,b);
if(a<b) arr[b] = a;
else arr[a] = b;
}
public static int findParent(int[] arr,int a, int b) { // 두 정점이 연결되어 있는지 확인하는 Find메소드이다.
// 마찬가지로 두 정점의 부모 정점을 메소드로 얻은 후,
a = getParent(arr,a);
b = getParent(arr,b);
// 두 정점의 부모 정점이 일치하면 연결되어 있는 것이고, 아니면 연결되어 있지 않은 것이다.
if(a==b) return 1;
else return 0;
}
public static void main(String[] args) {
int arr[] = new int[11];
for(int i=1;i<arr.length;i++) { // 최초의 정점은 자기 자신이 부모 정점이 된다.
arr[i] = i;
}
unionParent(arr,1,2); // 최초의 정점들의 상태에서 1번 정점과 2번 정점을 연결
unionParent(arr,2,3); // 위와 같다.
unionParent(arr,3,4);
unionParent(arr,5,6);
unionParent(arr,6,7);
unionParent(arr,7,8);
unionParent(arr,1,7);
System.out.println(findParent(arr,1,5));
}
}