유니온 파인드 Union find (JAVA)

📍 유니온 파인드란?

: 그래프/트리 알고리즘 중 하나로, 어떤 두 노드가 같은 집합에 있는지 확인하는 알고리즘이다. 서로소 집합(Disjoin-set)이라고도 한다.

union(x, y) 연산과 find(x) 연산으로 이루어져 있다.

1. 두 개의 연산

• Find: 주어진 요소가 속한 집합의 대표 노드(루트)를 찾는다. 이 연산을 통해 두 노드가 같은 집합에 속하는지 확인하는 데 사용된다.

• Union: 두 집합을 하나로 합친다. 이 연산은 두 집합을 연결하여 하나의 집합으로 만든다.

2. Union 연산

public void Union(int x, int y) {
	x = Find(x);
	y = Find(y);

	// 집합의 대표 노드(루트)가 같다면 같은 집합이라는 의미이다.
	if (x == y) return;

    // 합집합 경로 압축
	if (x < y) parent[y] = x;
	else parent[x] = y;
}

합집합 경로 압축(Union by Rank/Size) : union 연산에 활용되는 기법으로, 두 노드 중에 작은 노드를 큰 집합에 연결시켜준다. find 연산할 때 효율을 높여준다.

3. Find 연산

 public int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);  // 경로 압축
        }
        return parent[x];
    }

경로 압축(Path Compression) : Find 연산할 때, 모든 노드를 루트로 직접 연결하여 트리의 깊이를 줄이는 기법이다. 이를 통해 시간복잡도를 줄일 수 있다.