ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • [알고리즘 정리] Union-Find(유니온 파인드)
    Development/Algorithm 2020. 5. 3. 17:29

     

     

    다룰 내용

    • 서로소 집합이란 무엇인가?
    • 상호 배타 집합을 표현하는 방법
    • 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;
       }
    }

     

     

     

     

Designed by Tistory.