1 Week ] Union find

코세라 수업을 듣고 내가 정리한 내용이다.

 

Union find 알고리즘에 대해서 공부한 내용이다.

목차는 아래와 같이 5개이다.

 

1. dynamic connectivity

2. quick find

3. quick union

4. improvements

#5. applications # Union find 를 활용한 사례

 

 

1. dynamic connectivity

 

먼저 주어지는 N은 노드의 개수로 총 노드의 개수가 주어지고 이 노드들의 연결 정보가 입력값으로 주어진다.

이를 연결해주는 Union이라는 함수와 연결이 되어있는지 검사하는 find,connected 라는 함수를 만들어준다.

 

대략적인 클래스 모양은 아래와 같다.

public class UF // Union Find
    UF( int n ) // n개의 objects를 생성
    void union(int p, int q) // p,q 사이의 연결을 생성
    boolean connected(int p, int q) // p,q가 연결된 컴포넌트 인지 검사
    // int find(int p)
    // int count()

 

public static void main(String[] args)
{
    int N = StdIn.readInt();
    UF uf = new UF(N);
    while (!StdIn.isEmpty())
    {
       int p = StdIn.readInt();
       int q = StdIn.readInt();
       if (!uf.connected(p,q,))
       {
           uf.union(p,q);
           StdOut.println(p+" "+q);
       }
    }

 

2. quick find ( eager algorithm )

예제)

 

가지고 연결의 index 값이 동일하여 같은 배열에 있으면, 동일한 index를 가지고 있다고 판단하여,

 

id[] 0,1,1,3,3,0,0,1,3,3 각 최초 시작하는 index 값을 저장해도면 찾을 수 있다.

 

이 id 배열을 저장하여 두었을 때, 해당 값에 대해서 연결을 물으면 id 값이 다르면 연결성이 없다고 볼 수 있다.

 

하지만 이 접근방법은 숫자가 커진다면, 바꿔야하는 숫자도 많아져서 문제가 생긴다. 결국 제곱시간은 너무 느리다..

( 쉬운 구현이기 때문에 간단하게는 사용 가능 )

 

public class QuickFindUF
{
    private int[] id;
    public QuickFindUF(int N)
    {
        id = new int[N];
        for (int i = 0; i < N; i++)
            id[i] = i;
    }
    public boolean connected(int p, int q)
    { return id[p] == id[q]; }
    public void union(int p, int q)
    {
        int pid = id[p];
        int qid = id[q];
        for (int i = 0; i < id.length; i++)
            if (id[i] == pid) id[i] = qid;
    }
}

 

3. quick union ( lazy algorithm )

 

위의 quick find 알고리즘에서는 union에 많은 시간이 들어간다. ( 거의 무조건  N 만큼은 돌아가야함. )

 

이를 줄여보고자, quick union 알고리즘으로 만들어 본다.

 

id 배열에 연결되는 node의 root 값을 찾아가는 방법이므로, union의 속도가 빨라질수 있다.

 

이 방법은 결국 들어오는 왼쪽의 노드를 오른쪽의 노드 밑에 붙이는 만드는 방법으로 계속 트리가 늘어날 수있다.

public class QuickUnionUF
{
    private int[] id;
    
    public QuickUnionUF( int N )
    {
        id = new int[N];
        for (int i=0;i<N;i++) id[i]=i;
    }
    
    private int root(int i)
    {
        while (i != id[i]) i= id[i];
        return i;
    }
    
    public boolean connected(int p, int q)
    {
        return root(p)==root(q);
    }
    
    public void union(int p, int q)
    {
        int i = root(p);
        int j = root(q);
        id[i]=j;
    }
}

 

이 알고리즘은 quick find 보다는 빠를 수 있지만, quick union도 너무 느린 알고리즘이다.

 

Algorithm	initialize	union	find
quick-find	N	N	1
quick-union	N	N	N ( worst case )

 

quick-find의 단점은 union 작업시 N 만큼 걸리는 것이고,

quick-union의 경우 find 작업시 최대 N 만큼 걸릴 수 있게 되어 속도가 둘 다 좋지는 않다. ( 아주 긴 tree 모양이 될 때,)

 

그래서 quick-union을 개선시킨 방향을 생각해본다.

 

4. quick-union improvements

 

개선방향으로는 union 함수를 수행할 때, weighting을 비교하여 tree가 길어지지 않게 만드는 방법이다.

 

이렇게 되면, tree는 한쪽으로 치우쳐지지 않고, 분배되는 tree로 만들어지게 된다.

 

public class QuickUnionUF
{
    private int[] id;
    private int[] sz;
    
    public QuickUnionUF( int N )
    {
        id = new int[N];
        for (int i=0;i<N;i++) { id[i]=i; sz[i]=1;}
    }
    
    private int root(int i)
    {
        while (i != id[i]) i= id[i];
        return i;
    }
    
    public boolean connected(int p, int q)
    {
        return root(p)==root(q);
    }
    
    public void union(int p, int q)
    {
        int i = root(p);
        int j = root(q);
        // 추가된 코드
        if (i==j) return;
        if (sz[i]<sz[j]) { id[i] = j; sz[j]+= sz[i];}
        else { id[j] = i; sz[i]+= sz[j];}
    }
}

 

Algorithm	initialize	union	find
quick-find	N	N	1
quick-union	N	N	N ( worst case )
quick-union improvements	N	log N	log N

 

 

여기서 좀 더 발전적인 방향으로 path compression ( 루트를 바로 상속받기 ) 방법으로 좀 더 줄일 수 있다.

 

현재는 한 비교되는 노드에 자식으로 들어가는데, 각자 최고 root에 대해 자식으로 들어가게 되면

더 평평하게 만들 수 있다. 아래는 root을 찾을 때 추가되는 코드이다.

 

private int root(int i)
{
    while (i!=id[i])
    {
        id[i]=id[id[i]];
        i=id[i]
    }
    return i;
}