Union-Find 알고리즘

목차

• 서로소 집합(Disjoint Set)
• Union-Find란?
• Union-Find 연산
  • Find(x) 연산
  • Union(x, y) 연산
• Union-Find 연산 최적화
  • 1. 경로 압축(Path Compression)
  • 2. 랭크(Rank) 최적화
• 마무리

서로소 집합(Disjoint Set)

서로소 집합(Disjoint Set)은 겹치는 원소가 없는 여러 개의 집합을 의미합니다.

서로소 집합 예시
{1, 2, 3}, {4, 5, 6}

Union-Find란?

Union-Find는 서로소의 집합을 유지하면서, 여러 개의 집합을 하나로 합치거나(Union), 특정 원소가 속한 집합을 찾는(Find) 연산을 빠르게 수행하는 알고리즘 입니다.

Union-Find 연산

Find(x) 연산

• x가 속한 집합의 대표(루트) 노드를 찾는 연산
• 해당 노드가 속한 트리의 루트 노드를 찾는 과정임.

Union(x, y) 연산

• x가 속한 집합과 y가 속한 집합을 하나로 합치는 연산
• 한 집합의 루트 노드를 다른 집합의 루트 노드에 연결하는 방식으로 수행

Union-Find 연산 최적화

기본적인 구현은 Find 연산이 최악의 경우 O(N)까지 걸릴 수 있습니다. 따라서 이를 최적화 하기 위해 경로 압축(Path Compression)과 랭크 최적화 기법을 사용합니다.

1. 경로 압축(Path Compression)

경로 압축 기법은 find(x) 호출 시, 재귀적으로 부모를 갱신하여 최상위 루트를 저장하는 방식입니다. 이를 적용하면 트리의 높이가 줄어들어, find 연산이 평균적으로 O(1)에 가까워집니다.

public int find(int x) {
	if(parent[x] != x) {
    	parent[x] = find(parent[x]);
    }
    return parent[x];
}

2. 랭크(Rank) 최적화

두 집합을 합칠 때, 항상 작은 트리를 큰 트리에 붙이는 기법입니다. 이를 적용하면 트리의 높이가 불필요하게 커지는 것을 방지할 수 있습니다.

private int[] rank;

public UnionFind(int size) {
	parent = new int[size];
    rank = new int[size]; // 각 집합의 깊이를 저장
    for (int i = 0; i < size; i++) {
    	parent[i] = i;
        rank[i] = 1;
    }
}

public void union(int x, int y) {
	int rootX = find(x);
    int rootY = find(y);
    
    if (rootX != rootY) {
    	if(rank[rootX])
    }
}

마무리

Union-Find는 그래프의 사이클을 찾을때 아주 빠른 시간내로 찾을 수 있습니다. 따라서 꼭 익혀야 할 중요한 알고리즘인 것 같습니다. 그리고 앞서 유니온 파인드를 설명할 때 최적화 방법까지 설명 드렸는데, 그냥 처음부터 최적화된 방법으로 이해해주시면 앞으로 코딩 인생에 더 좋지 않을까 생각됩니다ㅎㅎ 설명이 필요하시다면 언제든 댓글 달아주시면 감사하겠습니다☺️ 다들 수고하셨습니다:)