유니온 파인드(UNION-FIND) 파이썬 / 자바 구현

유니온 파인드(Union-Find)는 트리형태를 갖는 자료구조이다.

 

합집합 찾기 및 상호 배타적 집합(Disjoint-set)이라고도 한다. 이름 그대로 상호 배타적인 부분 집합들로 나누어진 원소들을 저장하고 조작하는데 사용된다.

 

유니온 파인드(Union-Find)의 기능에 대해서 설명해보겠다.

1) Union : 두 집합을 하나의 집합으로 합치는 연산

2) Find : 어떤 원소 x가 주어졌을 때 이 원소가 속한 집합을 반환

위와 같이 두 가지 연산을 해주는 자료구조라고 할 수 있다.

 

정의를 알았다면 구현을 해보자 !

 

구현

1. 초기화

parent 배열을 만들어준다.

 

파이썬

parent[a] = b
#배열은 a 원소의 부모는 b이다. 라는 뜻으로 해석하면 된다.

#초기화 시작
parent[i] = i #자신의 부모는 자기 자신

 

자바

private static void make() {
		for(int i=0;i<N;i++) {
			parents[i] = i;
		}
}

 

 

 

2. Find 연산

 

파이썬

def find(x):
	if parent[x] == x: # x가 루트노드이면 자기 자신 반환
    	return x
    retrun find(parent[x]) # x가 루트가 아니라면 재귀를 이용해 루트노드를 찾는다.

위의 함수는 find 를 구현한 함수이다.

위와 같이 구현했을 때 여러 번의 find 연산이 반복되어 효율이 떨어진다.

이 문제를 해결하기위해 아래와 같이 find 함수를 바꿀 수 있다.

def find(x):
	if parent[x] == x:
    	return x
    parent[x] = find(parent[x])
    return parent[x]

메모이제이션 아이디어와 같은 것으로,

x의 부모를 find(parent[x])의 값으로 바꿔준다.

 

자바

private static int find(int a)	{
		if(a == parents[a]) return a;
		//자신이 곧 대표자이면 리턴
		
		return parents[a] = find(parents[a]);
	}

 

이렇게 find 함수 구현이 끝났다.

 

3. Union 연산

 

파이썬

def union(x, y):
	x = find(x) #x와 y의 루트노드를 찾아준다.
    y = find(y)
    if x == y: #루드가 같다면 합칠 필요가 없으니 종료
    	return
    parent[x] = y #x의 부모를 y로 만들어 합쳐주기
        

 

자바

public static boolean union(int a, int b) {
		int p_a = find(a);
		int p_b = find(b);
		
		if(p_a==p_b) return false;
		
		if(p_a<=p_b) p[p_b] = p_a; //작은게 부모가 되도록 통일시켜주기위해 !
		else p[p_a] = p_b;
		return true;
	}