Algorithm - Union&Find

Union & Find 알고리즘

• 서로 중복되지 않는 부분 집합 (Disjoint Set)을 표현할 때 사용하는 자료구조이다.

• 아래 코드를 예시로 확인 해보자.

   public class UnionAndFind {
  
       static int[] unf;
  
       // 해당 집합과 연관이 있는지 찾아주는 함수
       public static int Find(int v) {
           if ( v == unf[v] ) return v;
           else return unf[v] = Find(unf[v]);
       }
  
       // 매개변수 a 와 b 를 하나의 집합으로 만들어주는 함수
       public static void Union(int a, int b) {
           int fa = Find(a);
           int fb = Find(b);
           if ( fa != fb ) unf[fa] = fb;
       }
  
       public static void main(String[] args) {
           Scanner scan = new Scanner(System.in);
           int N = scan.nextInt(); // 인원 수
           int M = scan.nextInt(); // 친구 쌍의 갯수
           unf = new int[N+1]; // unf 라는 배열에 각 친구와 관련된 정보를 입력 할 것이기 때문에, 인원수 만큼 배열을 만듦 ( 0은 안쓸거임 )
           for ( int i=1; i<=N; i++ ) unf[i] = i; // 우선, idx = 친구번호로 초기화
           for ( int i=1; i<=M; i++ ) { // 친구 쌍 입력
               int a = scan.nextInt();
               int b = scan.nextInt();
               Union(a, b); // a 와 b 는 친구니까, 하나의 집합으로 만들어라
           }
           int a = scan.nextInt();
           int b = scan.nextInt();
           int fa = Find(a);
           int fb = Find(b);
           if ( fa == fb ) System.out.println("YES"); // unf[v] = Find(unf[v]); 이기 때문에 가능.
           else System.out.println("NO");
       }
  
   }
  

• 초기화 / 합치기 (Union) / 찾기 (Find) 세 가지 연산을 사용한다.

• 최소 스패닝 트리를 구현하는 크루스칼 알고리즘에 사용되며, 사이클을 만들지 않고 모든 노드를 방문할 수 있다

• 구현 방법은 다음과 같다. - 초기화 : N 개의 원소가 각각의 집합에 포함되어 있도록 초기화한다 -> 각각을 유일한 원소로 가지는 집합 생성

   - Union (합치기) : 두 원소 a, b 가 각각 속한 두 집합을 하나로 합친다 -> 두 개의 집합을 하나로 연결하는 역할
  	
   - Find (찾기) : 원소 a 가 주어질 때, 이 원소가 속한 집합을 루트노드를 반환한다 -> a가 어느 집합에 속해있는지 찾는 역할