[알고리즘] 유니온 파인드

1. 개념

여러 노드가 있을 때 특정 2개의 노드를 연결해 1개의 집합으로 묶는 union 연산과, 특정 원소가 속한 집합의 대표 원소를 반환하는 find 연산.

 

2. 연산

1) union

원소 a가 집합 A에 속해있고, 원소 b가 집합 B에 속해 있을 때 a와 b를 union한다는 것은 A와 B의 합집합을 구하는 것과 같다.

2) find

집합 A에는 다양한 원소들이 있고, 그 중에 a도 있다. find(a)는 a가 속한 집합에 있는 다양한 원소 중 대표 원소를 구하는 연산이다.

 

3. 원리

1차원 배열을 선언한다. 그 배열의 인덱스는 원소를 의미하고, 인덱스에 있는 값은 해당 원소가 속한 집합을 의미한다. 

1) find

1	2	3	4	5	6
1	2	3	4	5	6

find(1)은 1이 속한 집합의 대표 원소를 찾는 것을 의미한다. 이때 1차원 배열에서 인덱스 1(원소)과 인덱스 1에 있는 값(집합)을 비교한다. 만약 둘이 같으면 해당 원소가 속한 집합의 대표 원소가 바로 그 해당 원소이기 때문에 인덱스 1에 있는 값을 바로 리턴하면 된다.

1	2	3	4	5	6
1	1	2	4	5	6

find(3)을 한다고 해보자. 인덱스 3과 인덱스 3에 있는 값은 다르다. 이런 경우에는 인덱스 3이 가지고 있는 값을 인덱스로 해서 해당 인덱스로 가본다. 해당 인덱스가 2라서 거기로 갔더니 인덱스 2와 인덱스 2에 있는 값도 다르다. 그래서 인덱스 2가 가지고 있는 값을 인덱스로 해서 해당 인덱스로 간다. 해당 인덱스가 1이라 거기로 갔더니 드디어 인덱스 1과 인덱스 1에 있는 값이 같다. 그러면 find(3)은 1인 것이다. 그러면 인덱스 3에 있는 값도 1로 고친다.

위에 있는 표의 상황은 위의 그림과 같다고 이해했다. 먼저 union(2,3)을 했고, 그 결과와 1을 union한 것이다. 그런데 2의 대표 집합은 1로 수정을 했지만, 3의 대표 집합은 1로 수정을 못했고, find(3)을 하면서 수정을 완료하는 것.

1	2	3	4	5	6
1	1	2	3	4	5

위 상황은 대충 이런... 하지만 해당 원소가 속한 집합의 대표 값 수정은 2까지만 되어있는 것이다.

이때 find(5)를 한다고 하자. 인덱스 5와 인덱스 5가 가리키는 값이 달라서, 인덱스 5가 가리키는 값을 인덱스로 해서 이동한다. 그러면 인덱스는 4이다. 인덱스 4와 인덱스 4가 가리키는 값이 달라서, 인덱스 4가 가리키는 값을 인덱스로 해서 이동한다. 그러면 인덱스는 3이다. 인덱스 3과 인덱스 3이 가리키는 값이 달라서, 인덱스 3이 가리키는 값을 인덱스로 해서 이동한다. 그러면 인덱스는 2이다. 인덱스 2와 인덱스 2가 가리키는 값이 달라서, 인덱스 2가 가리키는 값을 인덱스로 해서 이동한다. 그러면 인덱스는 1이다. 인덱스 1과 인덱스 1이 가리키는 값이 같다. 그러면 5라는 원소가 속한 집합의 대표 원소가 1이라는 사실을 구할 수 있다. 

하지만 여기서 끝이 아니다. 우리는 계속 타고타고타고 하면서 내려와서 5라는 원소가 속한 집합의 대표 원소를 구했다. 그런데, 위에 그린 그림에서 볼 수 있듯이 타고타고 왔다는 것은 합집합을 의미하고, 결국 타고타고 온 원소들이 속한 집합의 대표 원소도 1이라는 사실을 알 수 있다. 그러니 우리는 타고타고 왔던 인덱스가 가리키는 값들을 모조리 1로 바꾼다. 

이를 경로압축이라고 하며, 이렇게 한 번 해 놓으면 다음번에 find 연산을 할 때의 시간복잡도는 O(1)이 된다. 예를 들어 위의 과정을 거치고 나면 인덱스 1~5까지의 값이 다 1이 되고, find(2)를 하면 상수 시간만에 값이 1이라는 사실을 구할 수 있다.

2) union

union(1,2)는 1과 2를 같은 집합으로 묶는 것을 의미한다. 즉 원소 1과 원소 2를 합치는 것이다. 이때, 둘을 합친 합집합의 이름은 둘 중 하나로 한다. 즉, 해당 합집합의 대표 원소가 둘 중 하나로 정해진다.

예를 들어 1과 2를 합하면서 합집합의 이름을 2라고 정했다고 하자. 1과 2가 합쳐진 집합이 존재하는데, 그 집합의 대표 원소가 2인 것이다. 그러면 이후에 원소 1과 3을 합치고 싶을 때 1이 속한 집합의 대표 원소를 찾아서 그것과 3을 합쳐야 한다. 이 과정에서 find 연산이 나오게 된다.

 

4. 구현

int[] parent = new int[N+1];

        for(int i = 1; i<=N; i++){
            parent[i] = i;
        }

public static void union(int a, int b){
    a = find(a);
    b = find(b);
    if(a!=b){
        parent[b] = a;
    }
}

public static int find(int a){
    if(a == parent[a]){
        return a;
    }else{
        return parent[a] = find(parent[a]);
    }
}

 

5. 관련 문제

백준 1717

GitHub - Lee-Min-Jung/coding_test_practice

백준 1976

GitHub - Lee-Min-Jung/coding_test_practice

백준 1043

GitHub - Lee-Min-Jung/coding_test_practice