분리집합 (Disjoint Set)

교집합이 존재하지 않는 둘 이상의 집합을 말하고 데이터 집합을 다룰 때 유용하게 쓰인다.

트리 구조와 차이점

• 트리 구조는 부모 노드가 자식 노드를 가리키는 형태
• 분리 집합은 자식 노드가 부모 노드를 가리키는 형태

또한 교집합이 없는 집합이기 때문에 차집합은 의미가 없다.

• Union-find 알고리즘을 사용
• 비트 벡터, 배열, 연결 리스트를 이용하여 구현이 가능하나 트리 구조가 가장 효율적

분리 집합의 연산은 다음과 같다.

• make-set(x)
  • 초기화 작업, x를 유일한 원소로 새로운 집합을 만든다.
• find(x)
  • x가 속한 최상위 부모 노드(루트 노드)를 반환한다.
• union(x, y)
  • x가 속한 집합과 y가 속한 집합을 합친다. (합집합)

static int[] parent; // 유니온 파인드 루트 노드 배열

// make-set 초기화 진행
parent = new int[N+1];
for(int i = 0;i<=N;i++) {
    parent[i] = i;
}

private int find(int x) {
    // 루트 노드는 부모 노드 번호로 자기 자신을 가지므로 같으면 리턴
    if(parent[x] == x) {
        return x;
    }

    // 각 노드의 부모 노드를 찾아 올라간다.
    return find(parent[x]);
}

private void union(int u, int v) {
    // 각 원소가 속한 트리의 루트 노드를 찾는다.
    u = find(u);
    v = find(v);

    if(u != v) {
        parent[v] = u;
    }
}

분리집합 연습 문제

• [ ] 집합의 표현
• [ ] 여행 가자
• [ ] 중량제한
• [ ] 거짓말
• [ ] 공항
• [ ] 백조의 호수
• [ ] 사이클 게임
• [ ] 친구비