Union-Find (합집합 찾기)Algorithm & Data Structure2020. 10. 27. 21:21
Table of Contents
main statement
Union_Find uf = new Union_Find(5);
uf.getParent(1);
uf.unionParent(1, 2);
uf.unionParent(2, 3);
uf.unionParent(4, 5);
uf.whoParent(1);
uf.whoParent(2);
uf.whoParent(3);
uf.whoParent(4);
uf.whoParent(5);
uf.hasSameParent(1, 2);
uf.hasSameParent(4, 5);
uf.hasSameParent(1, 5);
parent of 1 : 1
parent of 2 : 1
parent of 3 : 1
parent of 4 : 4
parent of 5 : 4
1 and 2 has same parent
4 and 5 has same parent
1 and 5 has different parent
==================코드 수정! ==========================
main
Union_Find uf = new Union_Find(5);
uf.union(1, 2);
uf.union(2, 3);
uf.union(4, 5);
System.out.println("============(1,2,3), (4,5) 결합============");
uf.whoParent(1);
uf.whoParent(2);
uf.whoParent(3);
uf.whoParent(4);
uf.whoParent(5);
uf.hasSameParent(1, 2);
uf.hasSameParent(4, 5);
uf.hasSameParent(1, 5);
System.out.println("============모든 원소 결합============");
uf.union(3, 4);
uf.whoParent(4);
uf.whoParent(5);
uf.seperate(3, "alone");
System.out.println("============3을 기준으로 분리============");
uf.whoParent(1);
uf.whoParent(2);
uf.whoParent(3);
uf.whoParent(4);
uf.whoParent(5);
union find
package Algorithms;
public class Union_Find {
int[] parent;
public Union_Find(int n) {
// 0은 미용, 1~n 인덱스 사용
parent = new int[n+1];
for (int i =1; i<parent.length ; i++) {
parent[i] = i;
// System.out.printf("parent[%d] : %d \n", i, parent[i]);
}
}
// 부모를 넘어 조상님을 찾아주는 함수
int getParent(int x) {
if(parent[x] == x) return x;
parent[x] = getParent(parent[x]);
return parent[x];
}
void whoParent(int x) {
System.out.printf("parent of %d : %d \n", x, parent[x]);
}
// 서로 결합해주고 최고 부모를 결정해주는 함수
void union(int a, int b) {
a = getParent(a);
b = getParent(b);
if(a<b) reSetParent(b, a);
else reSetParent(a, b);
}
// 같은 조상을 가지는 지 확인하는 함수
Boolean hasSameParent(int a, int b) {
boolean hasSame = getParent(a) == getParent(b);
String res = "";
res = String.format("%d and %d has", a, b);
if(hasSame) {
res += " same";
} else {
res += " different";
}
res += " parent";
System.out.println(res);
return hasSame;
}
// x를 기준으로 분리하는 함수, 12345가 있으면 예시는 아래와 같다.
// (123),(45) 혹은 (12),(345) 혹은 (12), 3, (45)
// 예를 들어 right 함수의 경우
// 설계상에 구현하기 난이도 있는 함수, 자기의 앞은 볼 수 있고, 뒤는 볼수 없기 때문에,
void seperate(int x, String where) {
if(where.equals("") || where.equals("left")) {
reSetParent(x + 1, x + 1);
}
else if(where.equals("right")) {
reSetParent(x, x);
// 어짜피 x보다 큰 인덱스만이 x를 부모로 가진다.
}
else if(where.equals("alone")) {
parent[x] = x;
reSetParent(x+1, x + 1);
}
else {
throw new IllegalArgumentException("공백, left, right, alone 중에 입력 부탁 드립니다.");
}
}
// 부모를 다시 재 정의해주는 함수, 자기 자신을 포함하면 self가 "self", 아니면 "none"
private void reSetParent(int center, int toBeParent) {
int oldParent = getParent(center);
for(int i= center; i<parent.length; i++) {
if(oldParent == getParent(i)) {
parent[i] = toBeParent;
}
}
}
}
결과
============(1,2,3), (4,5) 결합============
parent of 1 : 1
parent of 2 : 1
parent of 3 : 1
parent of 4 : 4
parent of 5 : 4
1 and 2 has same parent
4 and 5 has same parent
1 and 5 has different parent
============모든 원소 결합============
parent of 4 : 1
parent of 5 : 1
============3을 기준으로 분리============
parent of 1 : 1
parent of 2 : 1
parent of 3 : 3
parent of 4 : 4
parent of 5 : 4
내 전 블로그에 달린 댓글 !
'Algorithm & Data Structure' 카테고리의 다른 글
단기 코딩테스트 브론즈1에서 실버3까지 (0) | 2023.07.25 |
---|---|
파일 비교 알고리즘을 만들면서 참고한 자료들, (0) | 2020.10.27 |
DP (Dynamic Programming) (0) | 2020.10.27 |
알고리즘 테스트기 : Heap, Counting (0) | 2020.10.27 |
@philo0407 :: Philo의 다락방
hi hello... World >< 가장 아름다운 하나의 해답이 존재한다
포스팅이 좋았다면 "좋아요❤️" 또는 "구독👍🏻" 해주세요!