서로소 집합(Disjoint Set) & 유니온 파인드(Union Find) (with. Java)

서로소 집합(Disjoint Set) 이란?

서로소 집합은 서로 공통 원소가 없는 둘 이상의 집합들을 의미한다.

고등학교 때 반 별로 나눠 운동회를 진행했던 것을 생각하면 이해가 쉬울 것같다.

보통 가장 효율적인 트리 구조를 이용해서 구현한다.

유니온 파인드란(Union Find) 이란?

유니온 파인드는 서로소 집합을 만들 때 사용하는 알고리즘이다.

각 집합에는 대표 번호를 가지며 2가지 연산을 통해 두 집합을 합치거나 해당 집합의 대표 번호를 찾을 수 있다.

• union(a, b): a와 b의 집합을 합친다.

• findSet(a): 대표번호(트리에서는 최상위 부모)를 찾아 반환한다.

  💡

  findSet의 경로 압축

  findSet구현 시 경로 압축을 사용하여 속도를 더 빠르게 할 수 있다

  경로 압축을 사용하지 않은경우, 트리 구조가 한 쪽으로 치우쳐 LinkedList같은 모양이 나온다면 O(N)이 된다.

  하지만 경로 압축을 사용하는 경우, 대표번호를 찾기 위해 거쳐간 관련 경로의 대표번호 정보를 최종 대표번호 업데이트하여 깊이를 줄일 수 있다. 시간 복잡도는 평균적으로 O(α(N))이다.

  • α(N): 아커만 함수의 역함수. N이 얼마나 커지든지 매우 작은 상수 값을 가짐. (아주 큰 N값에도 빠르게 동작 가능)

구현 (Java)

int[] parents; // i번째 멤버의 부모 정보들

// 자기자신을 부모로 세팅 (멤버 번호는 0부터 시작해서 N-1로 끝남)
void makeSet(int n) {
    for (int i = 0; i < n; i++) {
        parents[i] = i;
    }
}

// a멤버에 대한 부모 찾기
int findSet(int a) {
    if (a == parents[a]) { // 자기자신이 최상위 부모라면 종료
        return a;
    }
		// 상위 부모 탐색 재귀로 탐색
    return parents[a] = findSet(parents[a]); // 경로압축 O: O(α(N))
    // return findSet(a); // 경로압축 X: O(N)
}

// a의 집합과 b의 집합을 같은 집합으로 묶기
void union(int a, int b) {
    a = findSet(a);
    b = findSet(b);
    if (a != b) {
        parents[b] = a; // 부모가 다르면 a를 부모로 묶기 (사용에 따라 다른 방식으로 표현해도 됨)
    }
}

💡

백준 관련 문제

• 1043번 - 거짓말

Uploaded by N2T