[JAVA] Union-Find 알고리즘

 

Union-Find 알고리즘은 합집합을 찾는다는 의미를 가진 그래프 알고리즘이며, Disjoint Set(서로소) 알고리즘이라고도 부른다. 구체적으로 여러 개의 수가 존재할 때, 각 수에 노드를 매긴 후, 현재 선택한 두 노드가 서로 같은 그래프에 속하는지 판별하는 알고리즘이다.

 

Union-Find 알고리즘을 이용하여 다양한 고급 알고리즘을 활용할 수 있으니, 심화적인 그래프 알고리즘을 다루기 전에 반드시 짚고 넘어가야 하는 알고리즘이다.

 

---

위와 같이 무작위 순서로 연결되어 있는 수의 집합을 순서대로 연결하기 위해서는 각 숫자들은 자신보다 작은 수를 자식으로 가지고, 큰 수를 부모 노드로 가질 필요가 있다. 

 

출처: https://maluchisoft.com/wp/2020/09/24/cplusplus-union-find-algorithm/

 

이러한 노드의 순서는 두 개의 배열로 나타낼 수 있다.

 

Array1: 각 수의 노드를 가지는 배열

0

1

2

3

4

5

6

7

8

Array2: 각 수의 부모 노드를 가지는 배열

0

1

2

3

4

5

6

7

8

현재는 전체 수 모두가 자기 자신밖에 연결이 안 되어있는 상태이므로 각 노드는 자기 자신을 가리킨다. 

이제, 각각의 숫자는 자식 or 부모 노드가 되어 연결이 돼야 하는데, 부모를 합칠 때는 일반적으로 더 작은 쪽으로 합친다. 

즉, 3 까지만 진행을 해보면, 각각의 배열은 다음과 같은 상태가 되는 것이다.

 

Array1: 각 수의 노드를 가지는 배열

0

1

2

3

4

5

6

7

8

Array2: 각 수의 부모 노드를 가지는 배열

0

0

1

2

4

5

6

7

8

이렇게 3까지 자신의 부모 노드와 합쳤다. 0과 1은 동일한 부모 노드를 가지고 있기 때문에 서로 연결되어 있다는 것을 알 수 있다. 하지만, 여기까지만 봐서는 2와 0이 서로 연결되어 있는지 알 수 있는 방법이 없다. 

그렇기 때문에 우리는 각각의 노드가 어떤 노드를 부모로 가지는 지, 자기 자신을 부모로 갖는 0에 도달할 때까지 데이터를 재귀함수로 추적하여 확인해주어야 한다.

서로의 부모 노드가 같은 지 확인해주면, 다음과 같은 배열이 완성된다.

 

Array1: 각 수의 노드를 가지는 배열

0

1

2

3

4

5

6

7

8

Array2: 각 수의 부모 노드를 가지는 배열

0

0

0

0

4

5

6

7

8

 -> 즉, 동일하게 0을 부모로 가지는 노드인 0, 1, 2, 3 은 모두 연결되어 있다.

 

이 확인하는 과정을 거치고 나면, 비로소 n개의 노드가 서로 연결이 되어 있는 상태인지 확인할 수 있는 Union-Find 함수가 완성이 된다. 

 

코드로 한번 작성해보자.

---

◎Union_Find.java

package com.choonham;

public class Union_Find {

	public Union_Find() {

	}

	public int getParent(int parent[], int x) {
		if (parent[x] == x)
			return x; // 부모노드가 자기 자신일 경우, 재귀 stop
		return parent[x] = getParent(parent, parent[x]); // 아닐 경우 한번 더 진행
	}

	// 부모 노드의 크기를 비교 후 작은 값을 큰 값의 부모로
	public void unionParent(int parent[], int a, int b) {
		a = getParent(parent, a);
		b = getParent(parent, b);
		if (a < b)
			parent[b] = a;
		else
			parent[a] = b;
	}

	// 두 수가 서로 연결되어 있는 지 판단
	public boolean findParent(int parent[], int a, int b) {
		a = getParent(parent, a);
		b = getParent(parent, b);
		if (a == b)
			return true;
		else
			return false;
	}

}

◎Main.java

package com.choonham;


public class Main {
	public static void main(String[] args){
		Union_Find uf = new Union_Find();
		int[] parent = {0, 1, 2, 3, 4, 5, 6, 7, 8};
		
		for(int i = 0; i < 5; i++) {
			uf.unionParent(parent, i, i+1);
		}
		System.out.println("0 - 3?" + uf.findParent(parent, 0, 3));
		System.out.println("0 - 6?" + uf.findParent(parent, 0, 6));
	}
}

---

◎Output

 

위와 같이 각 노드가 서로 연결된 노드인지 확인할 수 있다.

포스팅 도입에서도 언급했듯, 이 Union-Find는 다른 심화 그래프 알고리즘의 기초가 되는 알고리즘이므로, 반드시 확실하게 알고 넘어갈 필요가 있다.

 

 

끝!