유니온 파인드 (Union - Find) 알고리즘
1. 유니온 파인드 알고리즘
유니온 파인드 알고리즘에 대해 알아본다.
여러 노드 존재 시, 임의의 두 개 노드가 서로 같은 그래프에 속하는지 판별한다.
1. 배열, 메소드 설명
일단 이 알고리즘에 사용되는 배열, 메소드를 설명하겠다.
1) parent[i] 배열
각 노드 i가 어떤 부모에 포함되는지 나타낸다.
노드가 6개 있을 때 처음에는 모두 연결되지 않는 상태이다.
자기 자신만을 집합의 원소로 가지고 있다.
그래서 다음과 같다.
2) find 메소드
find(a)
: a가 어느 집합에 포함되어 있는지 찾는다.
3) union 메소드
union(a,b)
: a와 b가 포함되어 있는 집합을 합친다.
2. union 실행
union(1,2) 를 실행해보자.
일반적으로 더 작은 값 쪽으로 합친다고 한다.
그래서 노드 2가 속한 부모가 1이 된다.
즉, 1과 2는 같은 그래프에 속하게 된다.
그러면 이제
union(3,4) 를 해보자.
union(2,4) 를 해보자.
결과는 아래와 같다.
아래와 같은 상황인 것이다.
그렇다면 위에서 (2,4) 를 실행했는데
왜 parent[4] = 2 가 아닌,
parent[3] 부분이 바뀐 걸까?
코드를 살펴보면 알 수 있다.
public static void union(int a, int b) {
a = find(a);
b = find(b);
if(a!=b) {
parent[b] = a;
}
}
union 메소드에 보면 find 메소드가 실행된다.
public static int find(int a ) {
if(a==parent[a]) {
return a;
}else {
return parent[a] = find(parent[a]);
}
}
각 과정을 차례대로 실행해보자.
1) union(1,2)
먼저 find(1), find(2) 가 실행된다.
find 메소드는 각 노드가 어느 집합에 포함되어 있는지 찾는다고 했다.
즉, 노드 1과 2가 어느 집합에 포함되어 있는지 찾는다.
자신이 속한 그래프의 부모를 표현하는 것이 parent 배열값이기 때문에
parent 배열값을 리턴하면 어느 집합에 포함되는지 알 수 있다.
그런데 1과 2는 다른 노드들과 연결되어 있지 않기에
parent[1] = 1 이고, parent[2] = 2이다
그래서 각각 parent 배열값인 1과 2를 리턴하는 것이다.
그 결과 find(1) =1, find(2) = 2가 된다.
1과 2가 다르기 때문에,
parent[2] = 1이 된다.
2) union(3,4)
이 경우도 마찬가지이다.
먼저 find(3), find(4) 가 실행된다.
그 결과 find(3) =3, find(4) = 4가 된다.
3과 4가 다르기 때문에,
parent[4] = 3이 된다.
3) union(2,4)
find(2), find(4) 가 실행된다.
역시 parent[2], parent[4] 를 리턴하면 된다.
그런데 이 경우는 위와 다르게 재귀함수가 실행된다.
먼저 find(2) 를 살펴보자.
parent[2] 가 리턴되지만, 그 값은 find(parent[2]) 이다.
find(parent[2]) = find(1)
=> find(1) = 1
즉, 재귀함수를 통해
find(2) = 1이 된다.
find(4) 를 실행하면
parent[4] 가 리턴되지만, 그 값은 find(parent[4]) 이다.
find(parent[4]) = find(3)
=> find(3) = 3
즉, find(4) = 3이다.
그러면 다시 union 메소드로 돌아와서 union(2,4) 를 실행할 때
find(2) = 1, find(4) = 3으로
값이 다르기 때문에
parent[3] = 1 이 된다.
즉 아래처럼 결과가 나오는 것이다.
결과적으로 parent[4] = 3 이지만,
4도 1과 같은 그래프에 있다.
그래서 나중에는 여러 메소드를 통해
parent[4] = 1 이 된다.
예를 들어
solve 메소드를 소개하겠다.
solve(a,b) 는
a와 b 가 같은 그래프에 속해있는지 확인한다.
solve(1,4) 를 해보자.
4) solve(1,4)
public static boolean solve(int a, int b) {
a = find(a);
b = find(b);
if(a == b) {
return true;
}else {
return false;
}
}
}
여기서도 find(1), find(4) 를 실행한다.
find(1) = 1 이다.
find(4) 는 parent[4] 를 리턴하지만, 그 값은 find(parent[4]) 이다.
find(parent[4]) = find(3) 이다
find(3) 은 parent[3] 을 리턴하지만, 그 값은 find(parent[3]) 이다.
find(parent[3]) = find(1) 이다.
find(1) = 1 이다.
최종적으로 find(4) 는 1 을 리턴하게 된다.
그리고 이 때
parent[4] = 1 이 된다.
그래서 아래와 같이 바뀐다.
3. parent 배열 값
위에서 union 을 실행해서 두 노드를 합칠 때
더 작은 값쪽으로 합친다고 했다.
즉 1과 2를 합칠 때 아래와 같이 parent[2] = 1 로 더 작은 쪽으로 합쳐진다
그 이유는 union 메소드에서 알 수 있다.
public static void union(int a, int b) {
a = find(a);
b = find(b);
if(a!=b) {
parent[b] = a;
}
}union(a,b) 에서
a = find(a)
b = find(b)
까지 진행하고 난 뒤
a와 b가 다르면
parent[b] = a 로 값이 변한다.
이 때 더 작은 값 쪽으로 합쳐지도록 해야 되는데,
b가 a보다 크다고 일단 가정해서
parent[b] = a 로 해주는 것이다.
그래서 처음 상태에서
union(1,2) 을 했을 경우는
find(1) = 1, find(2) = 2 라,
b>a 인 상태라서
parent[2] = 1이 잘 되었다.
즉, 더 작은 값 쪽으로 합쳐졌다.
하지만
만약 union(2,1) 을 하면
parent[1] = 2 가 된다.
이 경우는
find(2) = 2, find(1) = 1 로,
a= 2 , b =1 이다.
코드를 실행하면
parent[2] = 1 이 된다.
메소드에서는 b가 a보다 클 거라고 생각하고
parent[b] = a 를 실행하라고 했지만
여기서는 b가 a보다 더 작아서
그래프가 합쳐질 때 더 큰 값 쪽으로 부모가 합쳐졌다.
하지만 이렇게 parent[1] = 2 가 되어도 상관없다.
결국은 1과 2가 같은 그래프에 속해있음을 표현하고 있기 때문이다.
그냥 일반적으로 더 작은 값 쪽으로 합친다는 것 뿐이다.
2. 최종 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static int parent[];
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
parent =new int[7];
for(int i=1; i<=6; i++) {
parent[i] = i;
}
for(int i=0; i<N; i++) {
st = new StringTokenizer(br.readLine(), " ");
int one = Integer.parseInt(st.nextToken());
int two = Integer.parseInt(st.nextToken());
union(one, two);
}
for( int i=0; i<M; i++) {
st = new StringTokenizer(br.readLine(), " ");
int one = Integer.parseInt(st.nextToken());
int two = Integer.parseInt(st.nextToken());
System.out.println(solve(one, two));
}
}
public static int find(int a ) {
if(a==parent[a]) {
return a;
}else {
return parent[a] = find(parent[a]);
}
}
public static void union(int a, int b) {
a = find(a);
b = find(b);
if(a!=b) {
parent[b] = a;
}
}
public static boolean solve(int a, int b) {
a = find(a);
b = find(b);
if(a == b) {
return true;
}else {
return false;
}
}
}
만약 이 상태에서
3 2
1 2
3 4
2 4
1 4
1 2
를 실행시키면,
결과는
true
true
로 나온다.
참고 자료 :
https://brenden.tistory.com/33
[알고리즘] 유니온 파인드 (Union-Find)
유니온 파인드(Union-Find) ① 유니온 파인드란? ▷ 대표적 그래프 알고리즘으로 '합집합 찾기'라는 의미를 가지고 있습니다. ▷ 상호 배타적 집합(Disjoint-set)이라고도 합니다. ▷ 여러 노드가 존재
brenden.tistory.com