자바 Union-Find

Union-Find 알고리즘

서로소 집합 알고리즘과 같은 개념으로,
Disjoint Set 을 표현할 때 사용하는 자료구조다.

우리는 문제를 풀때 먼저 2가지 연산을 이해하면 된다.

1. Find

• X가 집합에 포함되어 있는지 찾는 연산

2. Union

• X와 Y를 합치는 합집합 연산
• 트리를 구성하는 건 O(1)이지만 루트를 찾아가는 건 O(N)

📒 그림 순차로 이해하기

위와 같이, 모두 독립적으로 자기 자신만을 집합의 원소로 가지고 있는다.

// 초기설정 배열
 for(int i=0; i< N; i++) {
     	group[i] = i;
 }

이때 Union(1,2)를 해준다면,

다음과 같이 arr[2]의 인덱스에 1이 들어가고 합쳐지는걸 확인 할 수 있다.

"이때, 우리는 번호가 더 작은 값 쪽으로 합치는걸로 한다."

 public static void union(int a, int b) {       
   if(a < b)
      group[b] = a;
   else
      group[a] = b;
}
        

이때 우리는 번호가 가장 더 작은 쪽으로 합쳐야하는데...
이를 어떻게 찾아낼까?

static int find(int x) {
	if(group[x] == x) return x;
	return find(group[x]);
}
    

재귀함수를 통해 그룹내에 가장 작은번호 즉, 그룹의 root가 되는 인덱스 값을 찾는다. 그리고 root를 찾으면 리턴한다.

🎈풀어본 문제

백준 알고리즘 ::: 1717번 집합의 표현

이때 나는 시간초과가 났다...
그래서 찾아본게 경로압축이다.

🖋 알아보기

Path Compression(경로 압축)

• Find 단계에서 할 수 있는 개선법
• 트리가 높이가 최대치인 경우

static int find(int x) {
	if(group[x] == x) return x;
	return (group[x] = findParent(group[x]));
}

내 코드는 위와 같이 수정되었다.