[알고리즘] 유니온 파인드 (union-find) - Java

본 포스팅은 Do it! 알고리즘 코딩 테스트 : 자바편을 참고하여 작성되었습니다.

---

1. 유니온 파인드

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

 

1.1. 핵심 이론

union, find 연산

    union 연산 : 각 노드가 속한 집합을 1개로 합치는 연산이다.
                         노드 a,b가 a ∈ A, b ∈ B일 때 union(a,b)는 A ∪ B이다.

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

 

2. 알고리즘 구현 방법

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

      

      

      

    
    

      <java />
    
	parent = new int [n+1];
        // 처음 모든 대표 노드는 자기 자신
        for(int i=1; i<parent.length; i++){
            parent[i] = i;
        }

 

 

❷ 2개의 노드를(a,b)를 선택해 각각의 대표 노드를 찾아 연결하는 union 연산을 수행한다. union 연산은 두 집합을 합쳐주는 것이다. 일반적으로 집합 A에 집합 B를 합치며, 아래 코드도 그렇다.

• a를 포함하는 집합 A의 대표노드를 find 연산을 통해 찾아, a에 저장한다.
• b를 포함하는 집합 B의 대표노드를 find 연산을 통해 찾아, b에 저장한다.
• a와 b가 같다면 이미 같은 집합이라는 의미로, 더 이상 union연산을 진행하지 않는다.
• 같은 집합이 아니라면, B집합의 대표 노드를 A집합의 대표노드로 지정한다.

2.1. union 구현 코드

      

      

      

    
    

      <java />
    
 // union - 대표 노드끼리 연결하기
    public static void union(int a, int b){
        // a원소가 포함된 집합의 대표 원소를 찾음
        a = find(a);
        b = find(b);
        // 같은 집합에 속하는지 체크
        if(a==b)
            return;
        // 같은 집합이 아니라면 합치기 진행
        // b 집합의 대표를 a 집합의 대표로
        parent[b] = a;
    }

 

 

❸ find 연산은 자신이 속한 집합의 대표 노드를 찾는 연산이다. find 연산은 단순히 대표 노드를 찾는 역할만 하는 것이 아니라 그래프를 정돈하고 시간 복잡도를 향상시킨다. 

 

 find 연산의 작동 원리

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

 

중요!

find 연산을 진행할 때 거치는 노드들이 대표 노드와 바로 연결되는 형태로 변경된다. 그렇기 때문에 추후 노드와 관련된 연산 속도가 O(1)로 변경된다. 즉 1 -> 4 -> 6 형태로 연결되어있던 집합에서 find(6)을 하면 6 <- 1 -> 4의 형태로 변경된다.

 

그렇기 때문에 find 연산을 진행하면 경로 압축의 효과를 볼 수 있다. 경로 압축이란 실제 그래프에서 여러 노드를 거쳐야 하는 경로에서 그래프를 변형해 더 짧은 경로로 갈 수 있도록 함으로써 시간 복잡도를 효과적으로 줄이는 방법을 말한다.

 

2.2. find 구현 코드

      

      

      

    
    

      <java />
    
public static int find(int a){
        if(parent[a] == a){
            return a;
        }
        parent[a] = find(parent[a]);
        return parent[a];
    }

 

 

예시로 union(5,9)의 과정을 그림으로 살펴보자.

 

union 과정이 끝나면 각 노드의 parent를 저장하는 리스트는 아래와 같이 집합 B의 대표였던 4와 find 연산을 거쳤던 9의 parent가  변하게 된다.

 

 

 

 

3. 전체 구현 코드

      

      

      

    
    

      <java />
    
import java.io.*;
import java.util.*;

public class Main {
    static BufferedWriter bw;
    static BufferedReader br;
    static int [] parent;

    public static void main(String[] args) throws IOException {

        parent = new int [n+1];
        // 처음 모든 루트는 자기 자신
        for(int i=1; i<parent.length; i++){
            parent[i] = i;
        }
        
        // union(a,b);

    }

    // union - 대표 노드끼리 연결하기
    public static void union(int a, int b){
        // a원소가 포함된 집합의 대표 원소를 찾음
        a = find(a);
        b = find(b);
        // 같은 집합에 속하는지 체크
        if(a==b)
            return;
        // 같은 집합이 아니라면 합치기 진행
        // b 집합의 대표를 a 집합의 대표로
        parent[b] = a;
    }

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

}