[알고리즘 설계] Union Find 사용시 주의사항

이 글은 유니온 파인드에 대해 이미 알고있다는 전제하에 적은 글입니다.

들어가며

오늘 알고리즘 문제를 풀던 중, 전혀 예상하지 못했었던 경우에 대한 것을 알게되어서 적어두려고 한다.

먼저 이 글을 쓰기 위한 문제의 배경에 대해 잠시 말하려고 한다.

입력으로 1 2 / 2 4 / 5 6 … 이런 식으로 두 수는 서로 같은 집합에 있다는 입력이 들어오면, 입력을 받으면서 1과 2를 유니온 파인드 알고리즘을 통해 union 시켰다.

그 후, 문제에 맞게 해결하기 위해 parent 배열을 출력해보았다.

먼저 알고리즘을 보자.

while(M-->0) {
    st = new StringTokenizer(br.readLine());
    int i = Integer.parseInt(st.nextToken());
    int j = Integer.parseInt(st.nextToken());
    merge(i,j);
}

이 부분이 입력을 받으며, merge 함수에 i,j를 넣어 merge 시키는 부분이다.

public static void merge(int n, int m) {
    n = find(n);
    m = find(m);
    if(n!=m) {
        p[n]=m;
    }
}

private static int find(int n) {
    if(n == p[n]) return n;
    return p[n]=find(p[n]);
}

이 부분은 누구나 다 아는 유니온 파인드 부분에 대한 코드이다.

내가 풀려고 했던 문제는 이렇게 서로 관계가 있는 숫자들을 계속해서 같은 집합에 union-find를 이용하여 넣고, 총 이 숫자들은 몇개의 집합으로 구성되어 있는지 구하는 문제였다.

처음에 나는 HashSet 메소드를 통해, 중복되지 않게 p[i]를 넣어가며 마지막에 HashSet 메소드의 size를 출력하는 식으로 결과를 냈다.

하지만, 결과가 예상 밖의 결과가 나왔다. 디버깅 하던 중, p배열의 값을 출력해봤는데 놀라운 결과가 나왔다.

입력을 통해 나는 모든 숫자의 루트가 p배열에 들어있을 거라고 생각했다.

결국 모든 숫자는 하나의 집합안에 속하게 되었지만, 하나의 집합에 속한 후, 여전히 find(i)의 갱신이 되지 않은 부분들이 존재하여, 루트가 아닌 자신의 부모만이 출력된 결과였다.

이 부분을 해결하기 위해서 세 가지 방법을 소개하려 한다.

1. p[i] 대신 find(i)를 사용해라

이렇게 p[i]가 루트값으로 아직 갱신되지 않은 경우 구하고자 하는 문제가 무엇인지에 따라 반례가 많이 생길 수 있다.

분명 모든 i의 값들은 하나의 집합에 속해있지만, 갱신이 안된 경우 p[i]에는 집합의 루트가 아닌 단순 자기의 부모가 써있을 수 있으므로, 원하고자하는 답이 루트일 경우, find(i)를 통해 구하자.

2. N만큼만 더돌아라.

merge가 끝난 후, p배열에 모두 i의 루트가 써있으면 좋겠는 경우, for문을 통해 find(i)를 딱 한번씩만 실행하자.

그렇게 for문을 돌고나면, p 배열에는 모두 그 집합의 루트 값이 들어가 있을 것이다.

3. i==p[i]를 써라.

이 부분은 이 문제에만 해당하는 내용인데, 서로 다른 집합의 개수를 구하려 할때 아까처럼, HashSet등에 p배열을 넣게되면서 실수가 발생할 수 있다.

이때, 서로 다른 집합의 개수는 결국 root의 개수를 구하면 되고, 루트 i == p[i]로 이미 구성되어 있을 것이다.

N만큼 더 돌기 싫으면서 집합의 개수를 찾고 싶다면, i==p[i]를 통해 개수를 찾자!