Union Find(유니온 파인드) - 연관 문제: 백준(1717번) 집합의 표현

대표문제: 백준 1717번 - 집합의 표현

https://www.acmicpc.net/problem/1717 

1717번: 집합의 표현

Union-Find(합집합 찾기)는 그룹 분할을 관리하는 자료 구조이다. 아래와 같은 함수를 기본적으로 갖도록 한다.

isSame(x,y): 요소 x, y와 같은 그룹(집합)에 속하는지 여부를 조사함

unite(x,y); 요소 x를 포함하는 그릅과 요소 y를 포함하는 그룹을 합친다. 

{1,3,5,7} , {2,4} , {6}

{1,3,5,7,2,4}, {6} (unite)

Union-Find 구조는 그룹 하나하나가루트 트리를 구성함으로써 실현할 수 있으며, 이진 트리일 필요가 없다.

unite 전 트리 : {1,3,5,7} , {2,4} , {6}

unite 후 트리 {1,3,5,7,2,4} , {6}

(그림에서는 0번 인덱스를 생략했다.)

isSame(x,y)와 unite(x,y)를 구현하기 위해서는 선택된 요소가 어떤 루트와 연결되어 있는지 알아야 한다. 

그렇기 때문에 unite(x,y)를 통해 요소들을 연결시킬 때 요소의 부모를 저장하는 par[] 배열이 있어야 한다.

인덱스 번호가 노드의 번호라 했을 때, par 배열은 아래와 같이 구성될 것이다.(-1은 root를 의미한다.) 

par = {-1, -1, 1, 1, 2, 1, -1, 5}

이러한 par 배열을 얻기 위해서는unite를 할 때마다 x와 y의 루트를 찾아내어 par 배열에 저장해야 한다. 

루트를  찾아내는 함수 root(x)가 필요하다. 

요소의 부모 요소를 따라가다 보면 루트를 만날 수 있다. 이를 위해 root는 최상위 부모 요소를 찾기 전까지는 재귀호출을 하며 탐색을 지속해야 한다. 

root(x){ if(par[x] == -1) return x;              else { return root(par[x]); } //root는 요소 x를 포함하는 그룹의 루트를 반환한다.

 요소의 루트를 연결하는 unite는 요소 x 가 속한 그룹의 루트와 요소 y가 속한 그룹의 루트를 찾아내어 y 그룹의 루트를 x그룹의 루트로 연결해주면 된다. (또는 x그룹의 루트를 y그룹의 루트로)

unite(x,y){    x= root(x);    y= root(y);    if(x==y){ return false; } // 이미 같은 그룹이라면 아무 수행도 하지 않는다.     par[y] = x; //x그룹 루트 값을 y의 부모 값으로 저장한다.  }

두 요소의 루트가 같은 지에 대한 판단을 하는 isSame함수는 두 요소의 루트를 찾아 비교한다. 

isSame(x,y){    return root(x) == root(y) ; }

unite(x,y)를 수행하면 x,y에 대한 루트를 재귀적으로 찾고, 이에 대한 값을 반환한다. 만약 x,y의 루트가 같다면 같은 그룹에 속한 것이기 때문에 unite를 수행하지 않고 종료된다. x,y의 루트가 다르다면 서로 다른 트리에 있는 것이기 때문에 x나 y의 부모 노드를 재지정하여 연결시킨다. par[y] = x; or par[x] = y;

 

isSame(x,y)를 수행하면 x와 y의 루트를 재귀적으로 찾아 둘의 루트 요소가 같은지 확인한다. 그렇다면 true, 아니라면 false를 리턴할 것이다. 

 

전체코드

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

import static java.util.Collections.swap;

class UnionFind{
    int[] par;

    //초기화
    public UnionFind(int x){
        par = new int[x];
        Arrays.fill(par,-1);
    }
    //루트를 구함
    int root(int x){
        if(par[x]== -1){ return x;}
        else return root(par[x]);
    }
    //x와 y가 같은 그룹에 속해 있는가(루트가 일치하는가)
    boolean isSame(int x, int y){
        return root(x) == root(y);
    }

    //x를 포함한 그룹과 y를 포함한 그룹을 병합함
    boolean unite(int x ,int y){
        //x,y를 각각 루트까지 이동시킴
        x= root(x);
        y= root(y);

        //이미 같은 그룹이라면 아무것도 하지 않음
        if(x==y){ return false; }
        
        //y를 x의 자식으로 만들기
        par[y] = x;
        return true;

    }
    //x를 포함한 그룹 크기
    int size(int x){
        return siz[root(x)];
    }
};

public class Main {

    public static void main(String[] args) throws IOException {
        UnionFind uf= new UnionFind(7);

        uf.unite(0,1);
        uf.unite(2,3);
        uf.unite(4,5);
        uf.unite(1,2);
        uf.unite(3,4);
        uf.unite(5,6);

//
//        uf.unite(1,2);
//        uf.unite(2,3);
//        uf.unite(5,6);
//        uf.unite(1,6);

        for(int i=0; i<7; i++){
            System.out.print(uf.par[i]+" ");
        }

    }
}

해당 코드에서 UnionFind라는 클래스를 선언하여 사용했지만, 클래스 없이 구현해도 동작한다.