Union-Find 이란?

• 상호 배타적 집합 또는 Disjoin-Set(서로소 집합)이라고 부른다.
  • 공통 원소가 없는 상호배타적인 집합들로 서로 중복되지 않는 부분 집합들로 나눠진 원소들의 데이터를 처리하기 위한 알고리즘이다.
• 즉, 여러 노드가 존재할 때 어떤 두 개의 노드를 같은 집합으로 묶어 주고, 어떤 두 노드가 같은 집합에 있는지 확인하는 알고리즘이다.

Union-Find 연산

• Union : 서로 다른 두 개의 집합을 하나의 집합으로 병합하는 연산

  • Union(x, y) : x와 y가 속한 집합을 합치는 연산, x와 y의 부모를 하나로 통일 시킨다.

  // Union (두 집합 합치기)
  public void union(int a, int b) {
    a = find(a);
    b = find(b);
    if (a != b) parent[b] = a; 
  }
  

• Find : 하나의 원소가 어떤 집합(대표 부모)에 속해있는지 재귀 호출로 구한다.

  • Find(x) : x가 속한 집합을 찾는 연산으로 부모 값을 반환한다.

  // Find (부모 찾기)
  public int find(int a) {
    if (parent[a] == a) return a;
    
    // a의 부모 노드가 자기 자신이 아닐 경우 
    // a 노드의 부모 값을 계속 재귀 호출하여 대표 부모 값(집합)을 찾는다.
    else return parent[a] = find(parent[a]); 
                                            
  }
  

→ 이때 parent는 초기 값이 자기 자신이다. 즉, parent[0] = 0, parent[1] = 1, … 이라는 의미!