유니온 파인드를 처음 접한건 학교 알고리즘 수업때 크루스칼 알고리즘 최소비용신장트리를 하면서 접하게 되었다.
그때는 간단한 사용법 정도만 알고 넘어갔지만 이번에 코세라 알고리즘 강의를 들으면서 좀 더 구체적으로 배우게 되었다
1.Dynamic connectivity
동적 연결
Union command : Connect to object
Find/connected query : Is there a path between two objects?
public class UnionCommand {
public static void main(String[] args) {
// TODO Auto-generated method stub
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);
}
}
}
}
사용처 :
네트워크 연결에서 p q 사이의 길이 있는지 밝혀낼 수 있음
디지털 사진(픽셀)
소셜 네트워크
컴퓨터 칩
OS
수학 집합의 원소
percolation
Reflexive – p is connected to q
p가 q에 연결되어있는 것이다
Symmetric – if p is connected to q, then q is connected to p
만약 p가 q에 연결되어 있다면 그 반대도 성립한다.
Transitive - if p is connected to q and q is connect to r then p is connected to r
p가 q와 연결되어 있고 q 가 r과 연결되어 있다면 p는 r과 연결되어 있다.
어려워 보이지만 간단한 논리이다.
이제 본격적인 union 알고리즘이다.
- Quick find 알고리즘
- iff는 If and only if 라는 뜻이다.
Interpretation : p and q are connected iff they have the same id
p와 q가 연결되어 있고 그들이 무조건 같은 id를 공유할 때
Find : Check if p and q have the same id
p와 q 가 같은 id를 가지고 있는지 확인한다
Union – to merge components containing p and q, change all entires whose id equals to id[p] and id [q]
p와 q를 합치기 위하여 id가 id[p]와 id[q]와 같은 모든 모든 원소를 변경한다
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;
}
}
}
public QuickFindUF
id라는 array를 선언한다.
그 후 각 array 의 index에 맞는 값을 id로 제공한다.
public boolean connected :
id[p], id[q]의 동일성을 점검한다
public void union(int p, int q) :
pid와 같은 id라면(p 안에 속해있다면) id를 qid로 바꾼다 (병합했기때문)
- Quick Union
Find : check if p and q have the same root
p와 q가 같은 루트, 즉 같은 그룹에 속해있는지 확인한다.
Union : to merge components containing p and q, set the id of p’s root to id of q’s root
p와 q를 합치기 위하여 p의 root의 id를 q root의 id로 변경한다.
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;
}
}
public QuickUnionUF(int N) :
id라는 array를 선언한다.
그 후 각 array 의 index에 맞는 값을 id로 제공한다.
private int root(int i) :
root의 id를 확인하여 id가 같이 않으면 root의 id를 id[i]로 변경한다
public boolean connected :
id[p], id[q]의 동일성을 점검한다
public void union (int p, int q) :
p와 q를 root를 통해서 id값을 변경하고 변수로 저장한다
그리고 id[i]를 j로 변경하여 p와 q를 병합한다.
하지만 이들의 시간복잡도는 O(N)으로 준수한 시간복잡도이나 큰 데이터가 온다면 시간이 너무 오래 걸리게 된다.
이에 Quick Union Advanced가 존재한다.
큰 트리와 작은 트리를 합할 때 큰 트리가 작은 트리 아래로 들어가서 비 효율적인 길이가 나오는것을 방지한다.
그러기 위해선 각 트리의 weight를 측정하고 트래킹하며 항상 작은 트리가 큰 트리 아래로 가도록 설정해야한다.
이는 복잡해 보이지만 의외로 간단하게 몇줄의 코드만으로 해결된다.
Find :
identical to quick union
return root(p = root(q);
Union modify q to :
Link root of smaller tree to root of larger tree
Update the sz [] array
항상 작은트리를 큰 트리에 링크하고 array를 업데이트 해야한다.
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[i] = I, sz[i] += sz[j];
}Depth of any node x is at most lg N
이렇게 작성된 트리의 길이는 lgN보다 클 수 없다.
이에 대한 수학적 증명은 나중에
다른 방법으로는 Path Compression이 있다.
union 과정이 전부 끝난 트리에서 하위노드들을 root노드에 연결하는것이다.
이를 경로 최적화라고 한다
시간복잡도
