Union-Find 알고리즘의 구현 (JAVA)

 

언제 사용하는가?

 

unoin-find 유니온 파인드 , 분리집합, 서로소 집합, 합집합등 다양한 이름으로 불리는

이 알고리즘은 그래프의 연결관계를 파악할때 아주 효과적인 알고리즘이다.

 

여러 노드가 존재한다고 가정할때 그중 두개의 노드를 선택해 연결되어 있는가를 확인할때

적용이 가능하다.

 

다음과 같이 그래프가 있다고 가정해보자.

 

 

이때 임의의 노드 1과 4를 골라 연결관계를 파악하고 싶다면 DFS/BFS 등 여러 탐색 알고리즘이 생각날것이다. 그러나 이러한 그래프가 지하철 노선도와 같이 매우 크다라고 가정할때 임의의 두점을 골라 연결관계를 위해 다른 탐색알고리즘을 사용한다면 가능은 하겠으나 시간이 매우 오래걸린단 단점이 있다.

바로 이럴때 유니온파인드 알고리즘을 사용하면 효과적으로 두 노드의 연결관계를 파악할 수 있다.

 

 

어떻게 사용하는가?

 

우선 그래프는 대표노드를 갖는다 가정한다. 그리고 이 대표노드는 일반적으로 연결된 노드중 작은 값을 갖는 노드를 대표노드로 생각한다.

 

그럼 위의 그래프를 정리하면 다음 표와 같이 나타낼수 있겠다.

 

노드 번호	1	2	3	4	5	6
대표 노드	1	1	3	3	5	2

 

 

이제 1과 6의 연결관계를 보고싶다면 대표노드를 확인하면 된다.

먼저 1은 대표노드가 1 자기자신이므로 더 이상 확인할필요없다.

그리고 6의 경우 대표노드가 2이고, 2는 대표노드가 1이므로

1의 대표노드인 1과 동일 한 대표노드를 갖고 있음을 확인할수 있고

두 노드는 연결 관계임을 확인할수 있는것이다.

 

이때 1,2,6의 경우를 보면 1 >> 2 >> 6 으로 연결된 형태 이므로 재귀적으로 구현하는 경우 6이후로 더 많은 그래프가 연결된다고 가정하면 깊은 재귀로 갈수 밖에 없게 된다. 따라서 대표노드의 값을 갱신해줄 필요가 있다. 대표노드는 더 작은 값을 갖는 노드의 값을 대표노드로 한다고 했으므로 노드 6의 대표노드 또한 1로

갱신해줌으로서 재귀호출을 줄여줄수 있다.

 

이를 그림으로 표현 한다면 다음과 같다.

 

 

 

그리고 표로 표현한다면 다음과 같다.

 

노드 번호	1	2	3	4	5	6
대표 노드	1	1	3	3	5	1

 

 

이제 1과 6의 연결관계의 파악을 위해 대표노드를 본다면 그 과정이 더 단조로워짐을 알수 있다.

(1의 대표노드 1 == 6의 대표노드 1)

 

이게 유니온파인드 알고리즘의 전부다. 그럼 바로 코드로 구현해 보도록 하겠다.

 

 

구현

 

먼저 필드로 대표 노드를 저장할 배열을 하나 선언하도록 하겠다.

 

public class UnionFind {

	private int[] manager;
    
}

 

 

아직 대표노드의 초기값은 아직 연결관계에 대해 모르기 때문에 노드 자기자신이 되겠다.

 

	void clear(int n) {
		manager = new int[n + 1];
		for(int i = 1; i <= n; i++) {
			manager[i] = i;
		}
	}

 

 

이제 그래프의 대표노드를 가져오는 메소드를 작성해보도록 하겠다.

대표노드의 배열에서 자기자신이 나올때까지 재귀호출과 갱신을 해주면 된다.

 

	private int getManager(int node) {
		if(manager[node] == node) {
			return node;
		}
		return manager[node] = getManager(manager[node]);
	}

 

 

그리고 그래프의 연결과 대표노드의 갱신의 작업을 해줄 메소드를 만들어 주겠다.

인자로 연결할 두 노드를 받고 위에서 선언한 메소드를 사용해 각각 대표노드를 가져온뒤

더 작은 값을 갖는 대표노드로 갱신해주면 된다.

 

	void union(int a, int b) {
		a = getManager(a);
		b = getManager(b);
		if(a < b) {
			manager[b] = a;
			return;
		}
		manager[a] = b;
	}

 

 

이제 두 노드가 연결관계인지 확인할 메소드를 구현해보겠다.

인자로 받는 두 노드의 대표노드가 같다면 true, 다른경우 false를 리턴해줄수 있도록 했다.

 

	boolean find(int a, int b) {
		if(getManager(a) == getManager(b)) {
			return true;
		}
		return false;
	}

 

 

그럼 위에서 예시로 설명한 그래프를 적용해 연결관계를 파악해보도록 하겠다.

노드를 6개로 설정을 하고 연결된 간선을 표현해주고,

 

		UnionFind unionFind = new UnionFind();
		unionFind.clear(6);
		unionFind.union(1, 2);
		unionFind.union(2, 6);
		unionFind.union(3, 4);

 

 

이제 연결관계를 파악해보면, 

 

System.out.println(unionFind.find(1, 6));
System.out.println(unionFind.find(6, 5));

 

 

1번 노드와 6번 노드는 연결되어있으므로 true,

6번 노드와 5번 노드는 연결되어 있지 않으므로 false임을 확인 할수 있다.

이때 6번 노드와 연결된 1번 노드와 5번 노드를 연결하고

다시 6번 노드와 5번 노드의 연결관계를 파악해보겠다.

 

 

		System.out.println(unionFind.find(1, 6));
		System.out.println(unionFind.find(6, 5));
		unionFind.union(1, 5);
		System.out.println(unionFind.find(6, 5));

 

 

연결한 뒤에는 두 노드가 연결관계임을 확인할수 있다.

 

아래는 코드의 전문이다.

 

package unionFind;

public class UnionFind {

	private int[] manager;
	
	void clear(int n) {
		manager = new int[n + 1];
		for(int i = 1; i <= n; i++) {
			manager[i] = i;
		}
	}
	
	private int getManager(int node) {
		if(manager[node] == node) {
			return node;
		}
		return manager[node] = getManager(manager[node]);
	}
	
	void union(int a, int b) {
		a = getManager(a);
		b = getManager(b);
		if(a < b) {
			manager[b] = a;
			return;
		}
		manager[a] = b;
	}
	
	boolean find(int a, int b) {
		if(getManager(a) == getManager(b)) {
			return true;
		}
		return false;
	}
	
	public static void main(String[] args) {
		UnionFind unionFind = new UnionFind();
		unionFind.clear(6);
		unionFind.union(1, 2);
		unionFind.union(2, 6);
		unionFind.union(3, 4);
		
		System.out.println(unionFind.find(1, 6));
		System.out.println(unionFind.find(6, 5));
		unionFind.union(1, 5);
		System.out.println(unionFind.find(6, 5));
	}
}