유니온-파인드(Union-Find)

해당 글은 저자, 본인이 이해하기 위해서 쓴 글임을 밝힙니다. (공부하자!)

서로소 집합(Disjoint Set)

---

Disjoint Set(서로소 집합, 분리 집합)이란 서로 공통된 원소를 가지고 있지 않은 두 개 이상의 집합을 말합니다.(오!)

 

유니온-파인드(Union-Find)

---

유니온-파인드 알고리즘은 합집합 하고 해당 요소가 소속된 집합을 찾아내는(Find) 하는 알고리즘이다.

서로소 집합 알고리즘으로도 불리며, 노드 간의 연결 관계를 사용하는 등으로 자주 사용된다.

1. 기본 연산

• Union 연산 : 두 개의 집합을 하나의 집합으로 합치는 연산입니다. 즉, 한 트리의 루트를 다른 트리의 루트에 연결하여 두 트리를 하나로 결합합니다.
  1. find 연산을 통해 두 요소의 루트 노드를 찾음.
  2. 두 루트 노드중 하나를 다른 트리의 루트 노드 아래에 배치하여 두 트리를 합침.
  • 주의점!
    • 선형 트리가 생길수 있다.
    • Find 연산이 O(N)이 걸리게 된다.
• Find 연산 : 어떤 원소가 주어졌을 때 이 원소가 속한 집합의 대표 원소(=루트 노드)를 반환하는 연산입니다 이 연산은 대표 원소에 도달할 때까지 부모 배열을 재귀적으로 순회합니다.

2. 용도.

집합 소속 여부 판단. : 임의의 두 노드가 동일한 집합에 속해 있는지를 확인할 수 있다. 그래프 라면 임의의 두 노드가 연결되어 있는지를 판단할 수 있다.

경로 압축: Find 연산중 압축 기법을 사용하여, 그래프 내에서 노드간의 경로를 최적화할 수 있다. → 시간복잡도를 향상할 수 있다.

사이클 감지 : 그래프 탐색 중에 새로운 연결(Edge)이 사이클을 만드는지 감지할 수 있다.

• 그러나, 무방향 그래프에서만 적용 가능

3. 과정

- 1 Union 연산

여러 노드 중 두 노드를 선택하여 하나의 집합으로 연결 하려고 한다!

1차원 배열의 대표 노드를 갱신해주어 하나의 집합으로 묶는 과정이다.

*유의할 점! : Union 연산 시 항상 대표 노드끼리를 연결해주어야 한다.

1. 연결할 두 노드를 입력으로 받는다.
2. 두 노드의 대표 노드를 find()를 통해 찾는다.
3. 대표 노드끼리 union을 진행한다.

static void union(int x, int y) {
        int a = find(x);
        int b = find(y);
        if(a > b){
            parents[b] = a;
        }
        else{
            parents[a] = b;
        }
    }

-2 Find 연산

특정 노드의 대표 노드를 찾아내고, 대표 노드가 같으면 해당 노드들이 같은 집합에 속해 있는지를 확인할 수 있다. 이 연산은 대표 원소에 도달할 때까지 부모 배열을 재귀적으로 순회합니다.

 

초기의 find 연산은 자기 자신을 가리킨다.

 

병합된 집합이 있다면 그 집합의 대표 노드를 반환합니다.

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