[서로소 집합] 개요

이번 포스트에서는 서로소 집합(disjoint set)에 대해서 살펴보자.

 

서로소 집합

 

문제제시

https://www.acmicpc.net/problem/2606

 

서로소 집합이란?

서로소 집합(disjoint set)이란 상호 배타집합이라고도 불리며 서로 중복 포함된 원소가 없는 집합 즉 교집합이 없는 상태의 집합을 의미한다. 

서로소 집합은 집합에 속한 하나의 특정 멤버를 통해 각 직합을 구분하는데 이를 집합의 대표자(representative)라고 한다.

서로소 집합을 찾기 위한 알고리즘을 union-find 알고리즘이라고도 하는데 일반적으로 makeSet, findSet, union 3가지 메서드로 구성되기 때문이다.

 

서로소 집합의 연산과 표현

서로소 집합을 표현할 때는 연결 리스트를 활용하거나 배열을 이용할 수 있는데 일반적으로 배열을 주로 사용한다. 배열을 이용하는 방식은 자식 노드가 부모를 가리키며 부모 즉 루트 노드는 해당 집합의 대표자가 된다.

먼저 출발점은 makeSet으로 가장 기본적인 서로소 집합 만들기에서 시작한다. 가장 기본적인 서로소 집합이란 원소 하나 하나가 대표자가 되는 형태이다.

노드 스스로 각자 그룹의 대표자이다.

다음으로 집합들을 합쳐볼 수 있다. 만약 1과 2가 합치고 2와 3이 합쳐진다면 다음과 같이 대표자가 변경된다.

1과 2는 서로 관계가 있다. 3과 4도 서로 관계가 있다. 그럼 합치고 대표자를 변경한다.

대표자를 결정할 때는 특별한 규칙은 없다. 이제 1과 3이 각 그룹의 대표자가 되었다. 여기서 다시 두 집합이 합한다면?

최종 모습은 위와 같다. 이제 이 그룹의 대표자는 요소 번호와 대표자 번호가 같은 1번이고 나머지 요소는 꼬리에 꼬리를 물고 1번 요소를 가르킨다.

이런 동작을 위해 makeSet, findSet, union 연산을 사용한다.

서로소 집합의 연산

 

makeSet

makeSet은 말 그대로 집합을 만드는 연산이다. 가장 확실한 서로소 집합은 개별 요소들이 스스로 집합을 구성하는 형태이다. 따라서 makeSet 연산은 요소 하나 하나가 그룹의 대표자가 된다.

모두가 대표자!

static int[] src = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
static int[] repres = new int[src.length + 1];

// 각각의 멤버를 대표자로 하는 집합 생성
static void makeSet() {
    for (int i = 0; i < src.length; i++) {
        repres[src[i]] = src[i];
    }
}

 

findSet

findSet을 그룹을 판별하는 연산인데 어떤 요소의 대표자를 파악함으로 그 요소의 소속 집합을 판단한다. findSet은 기본적으로 재귀를 통해서 내가 속한 그룹의 최상위 노드를 찾아간다.

// x가 속한 그룹의 대표를 찾는다.
static int findSet(int x) {
    if(repres[x]==x) {                      // repres의 값과 x가 같다면 내가 대표
        return x;
    } else {                                // 그렇지 않다면 대표를 통해 다시 대표 확인
        return findSet(repres[x]);
    }
}

그런데 위와 같은 연산은 노드의 깊이가 깊어진다면 엄청난 연산을 유발할 수 있다.

만약에 4의 부모를 100번 찾는다면 무슨일이 일어날까?

만약 동일한 노드의 부모를 찾는 연산이 여러번 일어난다면 결과는 1일로 뻔한데 계속해서 4번씩 연산이 일어나게 된다. 이 경우 연산의 효율을 높이기 위해 Path Compression이라는 기법을 사용한다. Path Compression은 findSet을 실행하면서 모든 노드들이 직접 대표를 가리키도록 변경하는 것이다.

처음은 어쩔 수 없지만 두번째 4의 대표를 찾는다면 한방에!!

// x가 속한 그룹의 대표를 찾는다.
static int findSet(int x) {
    if(repres[x]==x) {         // repres의 값과 x가 같다면 내가 대표
        return x;
    } else {                   // 그렇지 않다면 대표를 통해 다시 대표 확인
        return repres[x] = findSet(repres[x]);
    }
}

 

union

union 연산은 두 그룹의 대표자를 하나로 변경해서 그룹을 통합하는 과정이다.

static void union(int x, int y) {
    // 각각 대표자를 데려온다.
    x = findSet(x);
    y = findSet(y);
   
    if (x == y) {         // 두 요소가 속한 그룹의 대표가 같다면 이미 같은 집합
        return;
    } else {              // 그렇지 않은 경우 한 녀석의 대표자를 다른 녀석으로 대체
        repres[y] = x;
    }
}

union find 자료구조는 circle이 존재하지 않는 구조이다. 따라서 union find의 union 과정에서 false가 리턴되면 circle이 존재한다는 의미이다.

 

바이러스

public class BJ_S2_2606_바이러스_서로소집합 {
    static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));

    static StringTokenizer tokens;

    private static int V, E;
    private static int[] p;

    public static void main(String[] args) throws IOException {
        input = new BufferedReader(new StringReader(src));
        V = Integer.parseInt(input.readLine());
        E = Integer.parseInt(input.readLine());
        makeSet();
        for (int e = 0; e < E; e++) {
            tokens = new StringTokenizer(input.readLine());
            int a = Integer.parseInt(tokens.nextToken());
            int b = Integer.parseInt(tokens.nextToken());
            union(a, b);
        }

        int cnt = 0;
        for (int i = 2; i < p.length; i++) {
            if (findSet(1) == findSet(i)) {
                cnt++;
            }
        }
        System.out.println(cnt);
    }

    private static void makeSet() {
        p = new int[V + 1];
        for (int i = 1; i < p.length; i++) {
            p[i] = i;
        }
    }

    private static int findSet(int x) {
        if (p[x] == x) {
            return x;
        } else {
            return p[x] = findSet(p[x]);
        }
    }

    private static void union(int a, int b) {
        a = findSet(a);
        b = findSet(b);

        if (findSet(a) == findSet(b)) {
            return;
        }
        p[a] = b;
    }

    private static String src = "7\r\n" +
                                "6\r\n" +
                                "1 2\r\n" +
                                "2 3\r\n" +
                                "1 5\r\n" +
                                "5 2\r\n" +
                                "5 6\r\n" +
                                "4 7";
}

 

서로소 집합의 기타 활용

 

각 서로소 집합의 크기

대표자의 대표자는 상징적의미(번호가 같으면 대표자다!)만 가지고 있는데 이 영역에 의미있는 숫자를 준다면 다른 용도로 활용이 가능하다. 대표자 노드의 대표자 값으로는 음수로 소속 노드의 개수를 저장한다면 손쉽게 소속 노드의 개수를 알 수 있다.

static void makeSet() {
    for (int i = 0; i < src.length; i++) {
        repres[src[i]] = -1;              // 자신의 번호가 아니라 소속 노드수 *-1
    }
}

이제 findSet의 과정에서 repres []의 값이 음수면 그 노드가 대표자가 된다.

static int findSet(int x) {
    if (repres[x] < 0) {                        // 대표자가 음수이면 내가 대표자
        return x;
    } else {                                    // 그렇지 않다면 대표를 통해 다시 대표 확인
        return repres[x] = findSet(repres[x]);
    }
}

마지막으로 union 과정에서 흡수되는 집합의 개수를 흡수하는 집합에 더해주면 된다.

static void union(int x, int y) {
    x = findSet(x);
    y = findSet(y);
    if (x == y) {
        return;
    } else {
        repres[x] += repres[y];        // x 그룹에 y 그룹의 요소들이 추가된다.
        repres[y] = x;                 // y의 대표자는 이제 x
    }
}