알고리즘 - Union-Find

Union-Find (합집합 찾기)

---

출처:https://velog.io/@agugu95/Java-Union-Find

유니온 파인드는 여러 노드가 있을 때 특정한 2개의 노드를 연결해 1개의 집합으로 묶는 union 연산과 두 노드가 같은 집합에 속해 있는지를 확인하는 find 연산으로 구성된 알고리즘입니다.

 

Disjoint-Set 알고리즘이라고도 불리며, 크루스칼 알고리즘에서 해당 간선이 사이클을 형성하는지 체크하는 데 사용됩니다.

 

 

🎈 연산 종류

---

유니언 파인드는 위에서 언급했듯이 이름 그대로 union 과 find 연산으로 이루어져 있습니다.

 

union 연산은 각 노드가 속한 집합을 1개로 합치는 연산으로, 노드 a,b가 a ∈ A , b ∈ B일 때 union(a,b) = A∪B 를 의미합니다.

 

find 연산은 특정 노드 a에 관해 a가 속한 집합의 대표 노드(최상위 부모)를 반환하는 연산으로 노드 a가 a ∈ A일 때, find(a) = A 집합의 대표 노드를 의미합니다.

 

 

🔨 구현 방법

---

일반적으로 1차원 배열을 이용하여 구현하게 됩니다.

 

 

1. 부모 노드(집합)를 체크할 배열 생성

 

각 노드가 연결되어있지 않다고 가정하고 부모 노드를 본인의 인덱스 값으로 초기화합니다.

1번 예시

노드 번호	1	2	3	4	5	6	7	8
부모 노드 번호	1	2	3	4	5	6	7	8

 

 

2. 2개의 노드를 선택 후, Union-Find 알고리즘 실행

 

2-1. 집합의 최상위 부모 찾기 = Find

 

집합을 하나의 트리라고 생각해 봅시다.

 

두 노드를 비교했을 때, 최상위 노드가 동일하다면 두 노드가 하나의 트리에 포함되어 있다는 것을 의미하므로 우선 연결된 노드들의 최상위 부모 노드를 찾습니다.

 

 

2번 예시, 1-2 간선

노드 번호	1	2	3	4	5	6	7	8
부모 노드 번호	1	2	3	4	5	6	7	8

1번 노드의 부모는 자기 자신, 2번 노드의 부모도 자기 자신입니다.

 

 

2-2. 두 노드를 합집합 = Union

 

두 노드가 간선으로 연결되어 있으므로 같은 트리(집합)에 있어야 합니다.

 

같은 트리에 존재하는 것은 최상위 노드(부모노드)가 동일하다는 것으로 알 수 있으므로, 각자의 부모노드 통일시켜 줍니다.

 

여기서 부모 노드는 find 연산으로 찾습니다.

노드 번호	1	2	3	4	5	6	7	8
부모 노드 번호	1	1	3	4	5	6	7	8

 

 

3. 2번 과정을 N-1번만큼 반복

3번 예시. 2-3 간선

 

노드 번호	1	2	3	4	5	6	7	8
부모 노드 번호	1	1	1	4	5	6	7	8

 

 

프로그래밍 언어로 구현

---

Java

public class UnionFind {

   // 배열 생성 , 따로 실행 코드에서 배열을 생성해도 됩니다.
   int[] parents;


   // 최상위 노드(부모) 찾기
   public static int find(int[] parents, int node) {
      // 자기 자신이 최상위 노드인 경우
      if (node == parents[node]) {
         return node;
      }

      // 자기 자신이 최상위 노드가 아닌 경우 = 집합이 존재할 경우
      // 재귀를 통해 최상위 노드를 찾아내고, 집합 내의 모든 노드들의 부모 노드를 최상위 노드로 갱신
      return parents[node] = find(parents, parents[node]);
   }

   // 합집합 연산
   public static void union(int[] parents, int nodeA, int nodeB) {

      int aParent = find(parents, nodeA);
      int bParent = find(parents, nodeB);

      // 부모 노드가 다르다면 합집합
      if (aParent != bParent) {
         parents[aParent] = bParent;
      }
   }
}