유니온 파인드(Union find) 알고리즘

개념

유니온 파인드란 합집합 찾기라는 의미로, 상호 배타적 집합(Disjoint set)이라고도 한다. 여러 노드가 존재할 때, 두 개의 노드가 서로 같은 그래프에 속하는지 판별하는 알고리즘이다.

해당 알고리즘은 find와 union 연산으로 이루어지며, find는 a가 어떤 집합에 포함되어 있는지 부모를 찾는 연산이고, union은 a와 b가 포함되어 있는 집합을 합치는 연산이다.

 

설명

노드 번호	1	2	3	4	5
부모 노드	1	2	3	4	5

만약 위와 같이 독립된 노드들이 있을 때 각 노드의 부모는 자기 자신이다.

노드 번호	1	2	3	4	5
부모 노드	1	1	3	4	5

이때 1과 2번 노드를 합친다(union)고 생각해보자. 부모를 합칠 때는 일반적으로 더 작은 노드를 기준으로 합치기 때문에 2의 부모 노드는 1이 될 것이다.

노드 번호	1	2	3	4	5
부모 노드	1	1	1	4	5

또 2와 3번 노드를 합쳐보자. 2의 부모는 1, 3의 부모는 3이다. 1 < 3이므로 3의 부모를 1로 변경해준다. 이제 1,2,3의 부모가 모두 1이라는 것을 통해 1,2,3 모두 같은 그래프에 속한다는 것을 알 수 있다.

 

구현

find 함수

public class UnionFind{
  public static int find(int n){
    //부모가 자기 자신이라면 그대로 리턴한다
    if(n == parent[n]) return n;
    //부모가 자기 자신이 아니라면 재귀로 현재 부모의 부모를 찾는다
    return parent[n] = find(parent[n]);
  }
  ...
}

 

union 함수

public class UnionFind{
  //10개의 노드가 있다고 가정한다
  //각 노드 번호를 그대로 쓰기 위하여 11의 크기로 초기화해준다
  public static int[] parent = new int[11];
  
  public static int find(int n){
    //부모가 자기 자신이라면 그대로 리턴한다
    if(n == parent[n]) return n;
    //부모가 자기 자신이 아니라면 재귀로 현재 부모의 부모를 찾는다
    return parent[n] = find(parent[n]);
  }
  
  public static void union(int x, int y){
    int px = find(x);
    int py = find(y);
    
    if(px < py){ //더 작은 쪽을 부모로 설정한다
    	parent[py] = px;
    }
  }
  
  public static void main(String[] args){
    //각 노드의 부모를 자기 자신으로 초기화한다
    for(int i=0; i<=10; i++) parent[i] = i;
  	
    union(1, 2);
    union(2, 3);
    
    String c1 = find(2) == find(3) ? "연결" : "비연결";
    String c2 = find(3) == find(4) ? "연결" : "비연결";
    
    System.out.print("2번 노드와 3번 노드는 "+c1+"되어 있습니다.");
    System.out.println("3번 노드와 4번 노드는 "+c2+"되어 있습니다.");
  }
}

2. 설명에서처럼 1번과 2번 노드를 연결하고 2번과 3번 노드를 연결한다. 그리고 노드가 연결되어 있는지 확인하였다.