유니온-파인드(Union-Find) 또는 서로소 집합(Disjoint Set)은 서로 중복되지 않는 부분 집합들로 나누어진 원소들에 대한 정보를 저장하고 조작하는 자료구조.

핵심 연산

• Find(x): 원소 x가 속한 집합의 대표 원소(루트)를 찾는다.
• Union(x, y): 원소 x가 속한 집합과 원소 y가 속한 집합을 합친다.

구현 방법

기본 구현 (배열 기반)

각 원소가 자신이 속한 집합의 대표 원소(부모)를 가리키는 배열을 사용

// 부모 테이블 초기화
int[] parnet = new int[n];
for (int i = 0; i < n; i++) {
	parent[i] = i; // 처음에는 자기 자신이 부모
}

// Find 연산
int find(int x) {
	if (parnet[x] == x) return x;
	return find(parent[x]);
}

// Union 연산
void union(int a, int b) {
	a = find(a);
	b = find(b);
	
	if (a < b) parent[b] = a;
	else parent[a] = b;
}

최적화 기법

• 경로 압축 (Path Compression)

  Find 연산 수행 시 거쳐간 모든 노드들이 직접 루트를 가리키도록 한다.

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

• 랭크에 의한 합치기 (Union by Rank)

  트리의 높이(랭크)를 기준으로 합친다.

  int[] rank = new int[n]; // 각 노드의 랭크(트리 높이)
  
  void union(int a, int b) {
  	a = find(a);
  	b = find(b);
  	
  	if (a == b) return;
  	
  	if (rank[a] < rank[b]) {
  		parent[a] = b;
  	} else {
  		parent[b] = a;
  		if (rank[a] == rank[b]) {
  			rank[a]++;
  		}
  	}
  }
  

시간 복잡도

• 기본 구현: 최악의 경우 O(n)
• 경로 압축만 사용: 평균적으로 O(log n)
• 경로 압축과 랭크에 의한 합치기 모두 사용: 거의 O(1)에 가까움 (정확히는 아커만 함수의 역함수인 a(n)으로, 실질적으로 상수 시간)