Union-Find 란?
-
그래프/트리 자료구조의 대표적인 알고리즘으로, 서로소 집합을 구할 때 사용한다.
-
Union() 메서도와 Find() 메소드로 이루어져있다.
Union(a,b) : 매개변수 a와 b를 같은 집합으로 만든다.
Find(x) : 매개변수 x가 어느 서로소 집합에 속하는지 구한다.
Union Find 문제 예시
-
입력으로 숫자 N이 주어진다.
(숫자 N은 순서쌍으로 나올 수 있는 숫자의 범위이다.
순서쌍에는 1 ~ N 까지의 숫자가 나올 수 있다.) -
입력으로 순서쌍이 주이지는데, 각 순서쌍은 서로 같은 집합이라 가정하자.
ex) (1,2), (2,3) 이 주어지면, 1-2-3은 같은 집합이다. -
하나의 순서쌍이 주어질 때, 두 매개변수가 같은 집합인지 구하라!
Find() : 매개변수가 어떤 집합에 속하는지 찾기
소스코드로 이해하기
static int[] unf;
public static int find(int x) {
if(x == unf[x]) {
return unf[x];
} else {
return find(unf[x]);
}
}
-
int[] unf : 나올 수 있는 수의 범위인 1 ~ N 으로 각각 다른 집합을 만든다.
N이 3이라면, 1, 2, 3이라는 3개의 집합이 만들어진다.
(즉, 어떤 수가 어떤 집합에 속하는지 알려주는 배열이다. 인덱스는 1부터 시작해 N으로 끝난다.) -
find()를 통해 해당 숫자가 어떤 집합에 속하는지 찾아온다.
만약 숫자와 숫자가 속한 집합의 번호가 같다면, 집합의 번호를 반환한다.
만약 숫자와 숫자가 속한 집합의 번호가 다르면, 집합의 번호에 해당하는 집합을 다시 찾는데, 이를 알기 위해 union() 메소드에 대해 알아보자.
Union() : 두 매개변수를 같은 집합으로 합치기
public static void union(int a, int b) {
int fa = find(a);
int fb = find(b);
if (fa != fb) {
unf[fa] = fb;
}
}- union() 메소드는 두 수를 같은 집합으로 만드는 메소드이다.
- 만약 집합의 번호가 다르면, 숫자 a의 집합 번호의 집합 번호를 숫자 b의 집합 번호로 바꾼다.
이는 a라는 숫자와 b라는 숫자와 같은 집합에 속하도록 하는것을 의미한다.
만약 입력으로 (1, 2)라는 순서쌍이 주어진다고 가정해보자.
숫자 1이 속한 집합은 1이다. (fa = 1)
숫자 2가 속합 집합은 2이다. (fb = 2)
fa 와 fb의 값이 다르기에 unf[1] = 2가 된다.
이 상태에서 만약 find(1)을 해보면, 1 != unf[1] 이기에 find(2)를 반환한다.
즉, 숫자 1은 집합 2번에 속하는 것을 알 수 있다.
문제 발생
- 이렇게 find() 메소드를 만들면 문제가 발생한다.
입력 순서쌍으로 (1,2), (2,3), (3,4) , ......로 연속적으로 순서쌍이 주어진다고 가정해보자.
해당 순서쌍들을 union() 메소드로 하나의 집합으로 합친 후 find(1)을 하면 어떻게 될까?
find(1) -> find(2) -> find(3) -> find(4) -> ..... 이렇게 계속된 탐색을 통해 find(1)의 값을 찾는 것을 알 수 있다.
그래프의 형태로 보면 1 - 2 - 3 - 4 - 5 - 6 - .... 와 같이 나온다.
이와 같은 그래프 형태에서 숫자 1과 숫자 1000000 이 같은 집합에 속하는지 알려면 너무 많은 시간이 걸린다.
find() 메소드 최적화
public static int find(int x) {
if(x == unf[x]) {
return unf[x];
} else {
return unf[x] = find(unf[x]);
}
}- 기존의 return find(unf[x])를 return unf[x] = find(unf[x])로 변경했다.
- 이는 기존 집합의 번호를 바꿔주는 작업이다.
예를들어 입력 순서쌍이 (1,2), (2,3), (3,4) , (4,5)가 주어진다고 가정하자.
기존 로직으로는 1- 2- 3- 4- 5와 같은 그래프가 만들어 진다.
바뀐 로직을 그대로 따라가며 순서쌍을 확인해보자.
만약 위와 같은 그래프에서 find(1)을 하면 어떻게 될까?
find(1) -> find(2) -> find(3) -> find(4) -> find(5) = 5
find(4) = 5
find(3) = 5
find(2) = 5
find(1) = 5결국 숫자 5에 1, 2, 3, 4가 모두 연결되어 있는 형태의 그래프가 나타난다.
이를 통해 추가적인 탐색을 거치지 않고도, 해당 숫자가 집합에 속하는지 바로 알 수 있다.
