[알고리즘 정리] Union-Find(유니온 파인드)

 

 

다룰 내용

• 서로소 집합이란 무엇인가?
• 상호 배타 집합을 표현하는 방법
• Union Find 구현

 

---

 

서로소 집합(Disjoint-set)이란?

서로소 또는 상호 배타 집합들은 서로 중복되는 원소가 없는 집합을 말합니다.

 

 

상호 배타 집합을 표현하는 방법

• 연결 리스트로 구현 
• 트리로 구현

 

상호 배타 집합 연산

• Make-set(x) : 집합을 만드는 동작입니다.
• Find-set(x) : x가 속한 집합을 찾는 동작입니다.(이때 해당 원소의 대표자를 반환합니다.)
• Union(x, y) : 두 집합의 원소를 주고 합치는 동작입니다.

 

상호 배타 집합 - 연결리스트 구현

1. 같은 집합의 원소들은 하나의 연결리스트로 관리합니다.
2. 연결리스트의 맨 앞의 원소를 집합의 대표 원소로 생각해봅니다.
3. 따라서 각 원소는 집합의 대표 원소를 가리키는 링크를 갖도록 구현합니다.

 

 

상호 배타 집합 - 트리 구현

1. 같은 집합의 원소들은 하나의 트리로 관리하게 됩니다.
2. 자식 노드가 부모 노드를 가리키며 루트 노드가 그 트리의 대표자가 되도록 구현합니다.

---

 

Union Find 구현

 

저는 트리 방식으로 Union Find를 구현해보았습니다. union을 호출하면 union 메소드 내부에서 find 메소드를 호출하여 각 원소의 가장 최상위 노드를 반환받습니다. 그리고 받은 둘의 부모 노드가 다르다면 합치고 같다면 합치지 않는 과정을 수행합니다. 같지 않다면 한 쪽의 부모 노드를 다른 쪽의 노드로 셋팅해줍니다.

그냥 단순히 한 쪽의 노드를 다른 쪽 노드의 자식으로 붙여도 무방하나, 이렇게 할 경우 depth가 깊어짐에 따라 부모 노드를 찾는 과정에 시간이 많이 소요됩니다. 따라서 합쳐질 노드의 부모를 그 트리의 root 노드로 설정을 해줍니다. 이렇게 하면 path 압축이 일어나 부모를 찾아 올라가는 시간을 단축할 수 있습니다.

 

package basic;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class UnionFind {
	
   public static int N, parents[];
   public static void main(String[] args) throws NumberFormatException, IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      N = Integer.parseInt(br.readLine());
      parents = new int[N];
      
      int cnt = Integer.parseInt(br.readLine());
      
      Arrays.fill(parents, -1); 
      
      while(cnt-- > 0) {
         String input[] = br.readLine().split(" ");
         int x = Integer.parseInt(input[0]);
         int y = Integer.parseInt(input[1]);
         
         if(union(x, y)) {
            System.out.println("합치기 성공");
         } else {
            System.out.println("이미 같은 집합임.");
         }
      }
      
      for (int i = 0; i < N; i++) {
         System.out.println(find(i));
      }
   }

   private static int find(int x) { 
      if(parents[x] < 0) return x; 
      return parents[x] = find(parents[x]); 
   }
   
   private static boolean union(int x, int y) { 
      int xRoot = find(x);
      int yRoot = find(y);

      if(xRoot != yRoot) {
      	 // path 압축
         parents[yRoot] = xRoot; 
         return true;
      }
      return false;
   }
}