[도구정리] Union-Find 알고리즘

문제 정의

백준 1976, 백준 1717번과 같은 문제들을 풀다 보면 팀을 만들거나, 동일한 하나의 부모를 바라보거나 하는 등의 종류의 문제를 마주칠 수 있다.

우리는 이 때 union-find라는 알고리즘을 적용하여 문제를 효율적으로 해결할 수 있다.

 

문제 접근

효율적은 알고리즘 파악을 위해 https://www.acmicpc.net/problem/1717 문제를 통해 알아보자.

 

첫 번째로, 문제는 0~n까지의 숫자를 각 집합으로 가지며 반복되는 과정 속에서 합집합을 통해 집합을 묶어나가고, 중간중간 두 원소가 같은 집합 내에 있는지 물어보는 것이다.

 

자. 여기서 우리는 합집합을 통해 집합을 묶어나간다는 부분에 집중해 보자.

 

[단계 1]

0	1	2	3	4

 

0~4까지의 숫자는 당연히 자기 자신을 부모로 바라보고 있을 것이다.

 

[단계 2]

0	1	2	3	4
0	1	2	3	4

 

다음과 같이 채워지게 된다.

이 문제에서 부모로 바라본다는 것은, 후반의 코드를 보면 더욱 이해가 쉽겠지만. 지금 당장은 그냥 몇 번째 집합인지라고 생각하자.

-> 0은 0번째 집합에 하나의 원소로 존재, 1은 1번째 집합에 하나의 원소로 존재!

 

[단계 3]

0	1	2	3	4
0	0	2	3	4

 

여기서 0과 1을 합집합 하라고 하면 어떻게 될까?

0과 1의 집합이 하나로 합쳐진다는 것으로 0번째 집합과 1번째 집합이 통일된다. 후에 그 집합 안에 0,1 두 개의 원소가 존재하게 된다.

0으로 통일되거나 1로 통일되거나 상관없지만 편의 상 앞 숫자인 0으로 통일된다고 생각하자.

그럼 위와 같이 1의 부모가 0으로 바뀌게 된다. (2가 2번째 집합에 있는 건 순서 상으로 만든 것일 뿐이니 1번째 집합으로 당겨야 하는 것 아닌가?라고 생각하지는 말자. 그냥 2번 집합이라고 하면 되는 것이다.)

 

[단계 4]

0	1	2	3	4
0	0	2	2	4

 

이번엔 2와 3을 합집합 한 것이다. 이 부분에 대해서는 중복되므로 건너뛰겠다.

0	1	2	3	4
0	0	0	2	4

 

(0,1)과 (2,3) 중 하나씩 뽑아 합집합을 이룬 결과이다. 즉, 4가지 경우의 수에서 다음과 같은 표가 나오게 된다.

왜 그렇게 될까? 1과 3을 합집합 했다고 생각하자. 그럼 위와 같은 과정과 유사하게 진행되지만 다른 부분은 딱 하나이다.  3의 부모가 바뀐 것이 아닌 2의 부모가 바뀐 것이다.

 

왜 그럴까? 이제 코드를 통해 봐 보자.

	// Union 연산
    public static void union(int a, int b) {
        int rootA = find(a);
        int rootB = find(b);
        if (rootA != rootB) { // 이미 같은 집합이 아닐 때만 병합
            if (rootA < rootB) { // 인덱스가 작은 것을 우선으로
                parent[rootB] = rootA;
            } else {
                parent[rootA] = rootB;
            }
        }
    }

    // Find 연산 (경로 압축 포함)
    public static int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]); // 경로 압축
        }
        return parent[x];
    }

 

다음과 같이 union-find 코드가 존재한다.

 

[단계 4]에 대해서만 같이 코드를 통해 알아보자.

union(1,3)이 실행 됐을 것이고, 각각 find(1), find(3)을 호출했을 것이다.

find(1)이 실행되면 parent [1] = 0 이기 때문에 find(0)이 실행되고, 이후 0이 반환될 것이다.

마찬가지로 find(3)이 호출되면, 2가 반환될 것이다.

 

union으로 돌아오면 x = 0, y = 2로 값이 변경된 상태이다. 아래의 조건문에 따라 x!=y이고, x < y이기 때문에 parent [2] = 0이 실행되며 union(1,3)이 끝난다.

 

0	1	2	3	4
0	0	0	2	4

 

엥?? 그럼 이 표가 유지되고 합집합이 제대로 안 된 것 아닌가??라는 생각을 할 수 있다. 할 거면 3까지 들고 갔어야지!!

-> 그렇기 때문에 최종적으로 여부를 판단할 때 단순 parent [3]으로 보는 것이 아닌 find(3)을 통해 보게 된다.

-> find(3)이 실행되면 find(2)가 실행되고, find(0)이 실행되어 0을 부모로 갖는다는 것을 찾게 되는 것이다!!