Union-Find (합집합 찾기)

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 

 

 

[Java] 문자열 비교하기 == , equals() 의 차이점

 

내 전 블로그에 달린 댓글 !