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;
}