알고리즘 - 서로소 집합 (Disjoint-set)

📒 서로소 집합

1️⃣ 서로소 집합 (Disjoint-set)

• 서로소 or 상호배타 집합들은 서로 중복 포함된 원소가 없는 집합들 (교집합 X)
• 집합에 속한 하나의 특정 멤버를 통해 각 집합 구분 → 대표자 (representative)
• 서로소 집합 표현 방법
  • 연결리스트
  • 트리
• 서로소 집합 연산
  • Make-Set(x)
  • Find-Set(x)
  • Union(x, y)

2️⃣ 서로소 집합 표현 - 연결리스트

• 같은 집합 원소를 하나의 연결리스트로 관리
• 대표 원소 : 연결리스트 맨 앞 원소 집합
• 각 원소는 집합의 대표 원소를 가리키는 링크를 가짐.

3️⃣ 서로소 집합 표현 - 트리

• 같은 집합 원소를 하나의 트리로 표현
• 대표 원소 : 루트 노드
• 자식 노드가 부모 노드를 가리킴

4️⃣ 서로소 집합 연산

• Make-Set(x)

  • 서로소 집합 초기화 작업

  • 유일한 멤버 x를 포함하는 새로운 지합 생성

    static void make() {
        for (int i = 0; i < N; i++)  parents[i] = i;
    }

• Find-Set(x)

  • x가 속한 집합 찾기 (대표자 찾기)

  • x를 포함하는 집합을 찾는 연산

    static int findSet(int a) {
        if (a == parents[a]) return a;
        return findSet(parents[a]);
    }

• Union(x, y)

  • x가 속한 집합과 y가 속한 집합의 합집합

  • x와 y를 포함하는 두 집합 통합

    static boolean union(int first, int second) {
        int firstRoot = findSet(first);
        int secondRoot = findSet(second);
        if (firstRoot == secondRoot) return false;
        parents[secondRoot] = secondRoot;
        return true;
    }

• 서로소 집합 동작 방법
  

📒 서로소 집합 - 최적화

1️⃣ 연산 효율 높이기

• Rank를 이용한 Union
  추가 내용
  • 각 노드는 자신을 루트로 하는 subtree 높이를 rank로 저장
  • 두 집합을 합칠 때 rank가 낮은 집합을 rank가 높은 집합에 붙임
  • 트리의 깊이에 따른 변화
    • 트리의 깊이가 다를 경우 깊은 트리에 낮은 트리 붙이기 (rank의 변화 X)
    • 트리의 깊이가 같을 경우 rank가 하나 늘어남.
• Path compression
  추가 내용
  • Find-Set을 행하는 과정에서 만나는 모든 노드들이 직접 root를 가리키도록 포인터 변경
  • Find-Set 연산은 특정 노드에서 루트까지의 경로를 찾아 가면서 노드의 부모 정보 갱신