유니온 파인드 & 백준 1717. 집합 표현하기

유니온 파인드

유니온 파인드는 여러 노드가 있을 때 특정 2개의 노드를 연결해 1개의 집합으로 묶는 union 연산과 두 노드가 같은 집합에 속해 있는지를 확인하는 find 연산으로 구성되어 있는 알고리즘입니다.

union 연산 : 각 노드가 속한 집합을 1개로 합치는 연산입니다. A = {a}, B = {b} 일 때, union(a, b)는 {a, b}가 되는 것을 의미합니다.

find 연산 : 특정 노드 a에 관해 a가 속한 집합의 대표 노드를 반환하는 연산입니다. 노드 a가 A = {a} 일 때 find(a)는 A 집합의 대표 노드를 반환합니다.

유니온 파인드의 원리

1. 유니온 파인드를 표현하는 일반적인 방법은 1차원 배열을 이용하는 것입니다. 처음에는 노드가 연결되어 있지 않으므로 각 노드가 대표 노드가 됩니다. 각 노드가 모두 대표 노드이므로 배열은 자신의 인덱스 값으로 초기화합니다.
   [1, 2, 3, 4]
   

2. 2개의 노드를 선택해 각각의 대표 노드를 찾아 연결하는 union 연산을 수행합니다.
   (1, 4) 와 (2, 3)을 union 연산으로 연결합니다. 배열[4]는 1로, 배열[3]은 2로 업데이트합니다. 이렇게 업데이트 하는 이유는 (1, 4)에 union연산을 하게 되면 1은 대표 노드로, 4는 자식 노드로 union 연산을 하므로 배열[4]의 대표 노드 값을 1로 변경한 것입니다. 그 결과 (1, 4)는 하나의 집합으로 합쳐집니다.
   [1, 2, 2, 1]
   

3. 이제 union 연산으로 3번과 4번 노드를 연결해 본다. 그런데 3, 4는 대표 노드가 아니다. 그래서 각 노드의 대표 노드를 찾아 find 연산으로 올라간 다음 그 대표 노드를 연결한다. 4의 대표 노드 1에 3의 대표 노드 2를 연결한 것이다.
   [1, 1, 2, 1]
   

find 연산의 작동 원리

1. 대상 노드 배열에 index값과 value 값이 동일한지 확인합니다.
2. 동일하지 않으면 value값이 가르키는 index 위치로 이동합니다.
3. 이동 위치의 index값과 value값이 같을 때까지 1~2를 반복합니다.반복이므로 이 부분은 재귀 함수로 구현합니다.
4. 대표 노드에 도달하면 재귀 함수를 빠져나오면서 거치는 모든 노드값을 루트 노드값으로 변경합니다.

find 연산은 시간 복잡도가 줄어드는 효과를 얻게 됩니다. 연산을 할 때 거치는 노드들이 대표 노드와 바로 연결되는 형태로 변경되기 때문에 추후 노드와 관련된 find 연산 속도가 O(1)로 변경됩니다.

백준 1717. 집합의 표현

문제

입력

첫째 줄에 $n$, $m$이 주어진다. $m$은 입력으로 주어지는 연산의 개수이다. 다음 $m$개의 줄에는 각각의 연산이 주어진다. 합집합은 $0$ $a$ $b$의 형태로 입력이 주어진다. 이는 $a$가 포함되어 있는 집합과, $b$가 포함되어 있는 집합을 합친다는 의미이다. 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산은 $1$ $a$ $b$의 형태로 입력이 주어진다. 이는 $a$와 $b$가 같은 집합에 포함되어 있는지를 확인하는 연산이다.

출력

1로 시작하는 입력에 대해서 $a$와 $b$가 같은 집합에 포함되어 있으면 "YES" 또는 "yes"를, 그렇지 않다면 "NO" 또는 "no"를 한 줄에 하나씩 출력한다.

풀이

위에서 배운 유니온 파인드 알고리즘을 구현하면 된다.
유니온 연산은 앞서 말했듯이 find 연산을 통해 둘의 대표노드를 찾아 대표 노드끼리 연결하면 되고(중요, 선택된 노드가 아닌 대표 노드끼리 연결한다는 것이 포인트), find 연산은 노드와 대표노드가 일치할 때까지 재귀로 반복하여 대표 노드를 찾으면 된다.

public static void union(int a, int b) { // union 연산 : 대표 노드끼리 연결하기

        a = find(a);
        b = find(b);

        if (a != b) {
            parent[b] = a;
        }

    }

public static int find(int a) { // find 연산

    if (parent[a] == a) {
       return a;
    }

    return parent[a] = find(parent[a]); // 재귀함수의 형태로 구현 -> 경로 압축 부분
    }