[알고리즘/JAVA/Union-find] 유니온 파인드

그래프 알고리즘 하위의 유니온 파인드(Union-Find) 알고리즘에 대해서 알아본다.

해당 알고리즘의 구성요소는 유니온(Union)과 파인드(Find)이다.

1. 개념

• 그래프 알고리즘
• "합집합 찾기" 라는 의미
• 서로소인 부분 집합 찾기
• 다수 노드 중에서 특정한 두 개가 서로 같은 그래프에 속하는지 판단하는 알고리즘
• union(x,y)와 find(x) 연산으로 구성됨
  • union(x,y) : x와 y 합치기. 즉, x와 y 노드의 각 부모를 합친다고 생각해야 한다.
    만약 union(3,4)라고 한다면, 3번 노드의 최상위 부모와 4번 노드의 최상위 부모를 합쳐야 하는 것이다.
  • find(x) : x가 어느 그래프에 속하는지 확인하기. 즉, x 노드의 부모들을 찾는 과정에서 부모가 없는 최상위 부모를 찾는 것이다.
    만약 find(4) 를 수행해본다고 가정한다. 그럼 4번 노드의 부모를 찾고, 3번 노드라는 사실을 확인한다. 다시 3번 노드의 부모를 찾으면 1번 노드이다. 그 다음으로 1번 노드의 부모를 찾으면 나 자신인 1번 노드가 부모 노드인 것이다. 따라서 1번 노드가 find(4)의 결과인 것이다.

2. 전제

• 다른 것과 연결되지 않은 노드는 혼자이다. 따라서 부모 노드(연결 노드)를 물어본다면, 나 자신이 된다.
• 유니온 파인드에서는 상대적으로 작은 숫자를 부모라고 선택한다. 1과 2를 합치기로 했다면, 1이 부모가 된다.
  3과 10을 합치기로 했다면, 3이 부모가 된다고 전제한다.

3. 유니온 파인드 예시

(1) 부모 노드 초기화

1번 ~ 5번 노드가 있다. 각 노드는 다른 노드들과 연결되지 않고, 자기 자신이 부모가 된다. 특정 노드 번호는 x라고 하면, x의 부모 노드를 확인하는 것은 parent(x) 로 수행할 수 있다.

(2) union(1,2)

1번 노드가 속한 그래프와 2번 노드가 속한 그래프를 합친다. 작은 숫자가 부모가 되므로, 2번 노드의 부모는 1번 노드가 된다. 수식으로 정리하면 parent(2) = 1 이 된다.

(3) union(3,4), union(3,5)

위와 같은 방식으로 parent(4)=3, parent(5)=3이 된다.

만약 2번 노드와 5번 노드의 부모를 찾으려면 find로 찾을 수 있다.
find(2) = 1, find(5) = 3이 된다.

(4) union(2,4)

2번 노드가 속한 그래프와 4번 노드가 속한 그래프를 합쳐야 한다. 즉, 2번 노드의 최상위 노드와 4번 노드의 최상위 노드를 합쳐야 하는 것이다. 각 노드의 최상위 노드는 아래와 같이 find 를 통해서 계산합니다.

• find(2) = 1
• find(4) = 3

결국 1번 노드와 3번 노드를 합치는 것이고 숫자가 작은 1번 노드가 부모 노드가 됩니다.

• find (4) = 1

4. Java로 구현한 유니온 파인드의 주요 함수

• Find 함수 : 특정 노드의 최상위 노드 리턴. 재귀 함수

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

• Union 함수 : 특정 노드 2개가 속한 그래프를 합치는 함수로써, 최상위 노드를 찾아서 합쳐야 한다. 각 노드의 최상위 노드는 find()로 찾아서, 부모값을 재설정한다.

public static void union (int x, int y) { // x와 y를 합치기
   x = find(x); // x번 노드의 최상위 노드 구하기
   y = find(y); // y번 노드의 최상위 노드 구하기

   if(x <= y) // x,y번 노드의 최상위 노드가 다르면 다른 그래프이므로, 합쳐야 한다.
      parent[y] = x; // y번 노드의 부모노드를 x번 노드의 부모노드로 교체한다.
   else
      parent[x] = y;
}

• IsSameParent 함수 : 특정 노드 2개가 같은 그래프인지 판단하는 함수로, 각 노드의 최상위 노드가 같은지 여부를 판단할 필요가 있으면 사용한다.

public static int isSameParent (int x, int y) {
   x = find (x) ; 
   y = find (y) ; 
   
   if (x == y) return 1;
   
   return 0;
}

5. Java 코드로 구현한 유니온 파인드 전체

public class main(){

   public static void main(String[] args) {
      int N = 5;
      parent = new int[N];

       //부모노드 초기화
      for (int i = 0 ; i < parent.length ; i++)
         parent[i] = i++;

      union(1,2);
      union(3,4);
      union(3,5);
      union(2,4);  
   }

   // union 함수
   public static void union(int x, int y){
      x = find(x);
      y = find(y);

      if(x <= y)
         parent[y] = x;
      else
         parent[x] =y;
   }

   // find 함수
   public static int find(int x) {
      if(parent[x] == x) return x;
      
      return parent[x] = find(parent[x]);

   }
}