Union-Find(유니온-파인드)

유니온-파인드는 disjoint sets라는 서로소 집합을 구하는 문제입니다. 서로소 집합이 용어는 어렵지만 공통 원소가 없는 집합들을 뜻합니다. 다음 그림을 보면 8개의 원소가 있고 서로소 집합은 3개입니다. 

 

https://en.wiktionary.org/wiki/pairwise_disjoint

 

다음과 같은 유형에서 사용하면 됩니다. (물론 DFS/BFS로도 풀이가 가능합니다!)

* 연결 정보가 주어졌을 때 2개의 원소는 서로 같은 집합에 속해 있는가?

* 연결 정보가 주어졌을 때 독립적인 섬의 갯수는 몇개인가?

 

Union-Find 관련 문제는 해당 원소들의 부모 정보들을 저장, 비교, 업데이트를 통해서 해결합니다. 따라서 각각 원소들의 부모 정보에 대해서 특별히 신경써주시면 됩니다. 

 

Union(결합시키다) : 해당 원소들의 parent를 비교하고 하나로 합칩니다. 

Find(찾다) : 해당 원소들의 parent를 비교하고 연결의 참/거짓을 확인합니다.

 

Union, Find와 더불어 각 원소의 최고 부모 원소를 찾는 getParent()까지 3가지를 구현하면 됩니다.

 

*주의할 점

합치는 과정에서 서로 다른 원소의 부모를 비교할 때 값이 더 작은 부모의 값으로 통일하면 편합니다.

ex) 2, 4 값을 합칠 때 2의 부모가 0이고 4의 부모가 1이면 부모를 0으로 통일합니다.

 

www.acmicpc.net/problem/1717

1717번: 집합의 표현

해당 문제를 해결하면서 적용해보겠습니다.

 

1. getParent() : 자신의 부모를 찾는다.

parent = new int[N+1];
for(int i=1;i<=N;i++) {
	parent[i] = i;
}

public static int getParent(int x) {
	if(parent[x]==x) return x;
	return parent[x] = getParent(parent[x]);
}

 

 

자신(x)	1	2	3	4	5	6
부모(parent[x])	1	2	3	4	5	6

 parent 배열을 정의하고 처음에 자신의 값이 곧 부모의 값과 같습니다.

또한 getParent() 함수는 재귀를 통하여 parent[x]==x일 때까지 계속 반복하여 얻어내면 됩니다. 우리는 이 유형에서 부모를 찾는 것이 중요하다고 했으므로 union과 find에 당연히 사용이 될 것이고 따라서 기본적으로 알아야 합니다.

 

2. unionParent() : 두 원소를 합친다.

public static void unionParent(int a, int b) {
	a = getParent(a);
	b = getParent(b);
		
	if(a<b) parent[b] = a;
	else parent[a] = b;
}

 위에서 언급한 getParent를 통해서 a,b 2개의 원소에 대한 부모를 찾습니다. 특히 주의할 점에서 썼다시피, 부모 값을 비교할 때 값이 더 작은쪽으로 합쳐주도록 합니다. 따라서 b가 a보다 클 경우 b의 부모는 a가 되고, 반대의 경우 a의 부모는 b가 됩니다.

 

3. findParent() : 두 원소에 대한 정보를 찾는다.

public static int findParent(int a, int b) {
	a = getParent(a);
	b = getParent(b);
		
	if(a==b) return 1;
	else return 0;
}

 위에서 언급한 getParent가 또 나왔습니다. 우리는 항상 부모의 값에 관심을 가지므로 먼저 부모를 찾아야 합니다. 이후 부모가 같다면 1을 반환하고 다르면 0을 반환하도록 하여 연관 관계를 확인합니다. 단순히 원소들의 관계에 대한 문제가 나올 수도 있고 독립적인 서로소 집합을 구하는 경우도 있습니다. 각 상황에 맞게 변형해서 사용하시면 됩니다.

 

import java.util.*;
public class bj1717_unionFind {
	
	static int N;
	static int M;
	static int parent[];
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		M = sc.nextInt();
		parent = new int[N+1];
		for(int i=1;i<=N;i++) {
			parent[i] = i;
		}
		
		for(int i=0;i<M;i++) {
			int status = sc.nextInt();
			int first = sc.nextInt();
			int second = sc.nextInt();
			if(status==0) {
				unionParent(first,second);
			} else {
				int ans = findParent(first,second);
				if(ans==1) System.out.println("YES");
				else System.out.println("NO");
			}
		}
	}
	
	public static int getParent(int x) {
		if(parent[x]==x) return x;
		return parent[x] = getParent(parent[x]);
	}
	
	public static void unionParent(int a, int b) {
		a = getParent(a);
		b = getParent(b);
		
		if(a<b) parent[b] = a;
		else parent[a] = b;
	}
	
	public static int findParent(int a, int b) {
		a = getParent(a);
		b = getParent(b);
		
		if(a==b) return 1;
		else return 0;
	}
}