유니온 파인드(Union Find)

개념

- 서로소 집합(Disjoint Set) 그리고 병합 찾기 집합(Merge Find Set)이라고도 불린다.

- 여러 노드가 존재할 때, 두 개의 노드를 선택하고 서로 비교하여 같은 그래프에 속하는지 판별하는 알고리즘.

- 부모 노드를 찾는 함수, 두 노드가 연결될 때 부모 노드를 변경해주는 함수, 두 노드가 같은 집합에 속하는지 판별할 수 있는 함수가 필요하다.

- 두 노드가 연결되어 부모 노드를 변경해줄 경우, 경로 압축 최적화를 위해 부모노드는 연결된 집합의 최상위 부모 노드를 참조하도록 설정한다.

 

public class union_find {

	//부모 노드를 찾는 메소드
	static int getParent(int[] parent, int x) {
		//x가 부모의 값과 동일할 경우 자신이 부모라는 의미.
		if(parent[x] == x) return x;
		
		return parent[x] = getParent(parent, parent[x]);
	}
	
	//두 부모 노드를 합치는 메소드(경로 압축 최적화를 위해 작은 값을 부모로 설정 )
	static 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;
		
	}
	
	//같은 부모를 가지는지 확인(같은 그래프에 속해있는지 확인)
	static int findParent(int[] parent, int a, int b) {
		a = getParent(parent, a);
		b = getParent(parent, b);
		
		if(a==b) return 1;
		else return 0;
		
	}
	
	public static void main(String[] args) {
		int[] parent = new int[11];
		
        for (int i = 1; i < parent.length; i++) {
			parent[i] = i;
		}
		
		 unionParent(parent, 1, 2); 
		 unionParent(parent, 2, 3);
		 unionParent(parent, 4, 5);
		 System.out.printf("1과 4는 같은 집합에 속하는가? %d\n", findParent(parent, 1, 4));
		 unionParent(parent, 1, 4);
		 System.out.printf("1과 4는 같은 집합에 속하는가? %d\n", findParent(parent, 1, 4));
		 
		 for (int i = 1; i < parent.length; i++) {
			 System.out.println(getParent(parent, i));
		 }
		
	}

}