유니온 파인드(Union-Find) 알고리즘
union(x, y)
연산과 find(x)
연산으로 이루어져 있음union(x, y)
: x와 y그래프를 합친다.find(x)
: x가 어느 그래프에 속하는지 연산한다.노드 1부터 5까지 있는 그래프가 있다.
위의 그림에서 노드 5개는 서로 연결되지 않고있다. 이 때 부모는 자기 자신을 가르키도록 한다. 이 단계를 보통 부모노드 초기화라고 부른다.
x
는 노드 번호이고, parent[x]
는 x
가 어떤 부모 노드에 속해있는지 알려준다.
1) union(1, 2)
parent[2] = 1
2) union(3, 4)
, union(3, 5)
parent[4] = 3
, parent[5] = 3
노드 2와 4의 부모 노드는 find로 찾을 수 있다.
find(2)
= 1
find(4)
= 3
3) union(2, 4)
parent[3] = 1
find(2)
= 1이고, find(4)
= 3이다. 노드 3은 노드 1보다 번호가 작으므로 노드 3의 부모노드는 1이 된다. find(x)
를 할 때 노드번호 x
와parent[x]
의 값이 같아야 하므로 노드 4의 find는 1이 된다.
find(4)
= 1
union 연산
public static boolean union(int x, int y) {
x = find(x); //x의 부모노드 찾기
y = find(y); //y의 부모노드 찾기
// 이미 같은 그래프에 속해있을 때 false 반환
if(x == y) return false;
if(x <= y) parent[y] = x;
else parent[x] = y;
return true;
}
find 연산
public static int find(int x) {
if(parent[x] == x) return x;
return find(parent[x]);
}
위의 예제 실행한 전체 코드
public class Main {
static int[] parent;
// union 연산
public static boolean union(int x, int y) {
x = find(x);
y = find(y);
if(x == y) return false;
if(x <= y) parent[y] = x;
else parent[x] = y;
return true;
}
// find 연산
public static int find(int x) {
if(parent[x] == x) return x;
return find(parent[x]);
}
// parent 출력
public static void parentPrint() {
System.out.print("[ ");
for (int i = 1; i < parent.length; i++) {
System.out.print(parent[i]+ " ");
}
System.out.println("]");
}
public static void main(String[] args) {
int n = 5;
parent = new int[n + 1];
// 부모 노드 초기화
for (int i = 0; i < parent.length; i++) parent[i] = i;
//위의 예제 실행
union(1, 2);
parentPrint();
union(3, 4);
parentPrint();
union(3, 5);
parentPrint();
System.out.println("find(2): " + find(2));
System.out.println("find(4): " + find(4));
union(2, 4);
parentPrint();
System.out.println("find(4): " + find(4));
}
}
출력 결과
[ 1 1 3 4 5 ]
[ 1 1 3 3 5 ]
[ 1 1 3 3 3 ]
find(4): 3
[ 1 1 1 3 3 ]
find(4): 1