[엮인 글 링크]
1-2 첫번째 방법: Quick-Find [Eager Approach]
1-3 더 나은 방법: Quick-Union [Lazy Approach]
앞서 살펴본 quick find가 너무 느렸기 때문에, 더 나은 대안이 필요하다.
다음으로 살펴볼 알고리즘은 quick union이다. quick find가 eager approach였던 대 비해, 이 방법은 lazy approach이다. lazy라는 이름이 붙은 이유는, 꼭 해야할 상황이 아니면 연산 수행을 피하기 때문이다.
quick union에서도 자료구조로 배열을 사용한다. 이 점은 quick find와 같다. 하지만 배열의 해석 방법은 다르다.
이 배열은 tree의 집합을 나타낸다. 배열의 원소들은 각 오브젝트의 parent 오브젝트, 자신보다 더 위에서 자신과 연결되어 있는 오브젝트를 나타낸다. 예를 들어 8의 parent는 6이고, 6의 parent는 5이다.
x = i일 때부터 반복적으로 id[x]의 값, 즉 부모 오브젝트를 구했을 때 부모가 자기 자신인 오브젝트가 i의 root이다.
예를 들어 오브젝트 8의 경우, id[8] = 6, id[6] = 5, id[5] = 5(부모가 자기 자신)이므로, 8의 root는 5이다.
이 자료구조에서 find/connected query와 union command를 수행해 보자.
1. find/connected query
quick union에서 같은 root를 갖는 오브젝트들은 서로 같은 connected component에 속해 있다. 위 그림을 예로 들면, 같은 connected component에 속한 오브젝트 0, 1, 2는 모두 root가 0이다. 그러므로 find query는 곧 root의 값을 구하는 것과 같다. root를 찾기 위해서는 오브젝트의 parent가 자기 자신일 때까지 parent를 찾아가면 된다. 이 메소드는 root에 도달할 때까지 계속 자신의 부모 오브젝트를 추적한다. 이 메소드를 실행하는 데에는 i 오브젝트의 깊이(depth)이만큼 배열 접근이 필요하다. '깊이'는 오브젝트가 뿌리로부터 몇 단계나 떨어져 있는지를 나타낸다.
1 2 3 4 5 | private int find(int i) { while (i != id[i]) i = id[i]; return i; } | cs |
connected query를 알아보자. p와 q의 root가 동일하다면, 둘은 서로 연결되어 있다.
ex) 2의 root는 0, 4의 root는 3이므로, 둘은 서로 연결되어 있지 않다.
8의 root는 5, 5의 root는 5로 서로 같은 root를 가지고 있다. 둘은 서로 연결되어 있다.
1 2 3 4 | public boolean connected(int p, int q) { return find(p) == find(q); } | cs |
2. union command
p와 q가 속한 두 개의 connected component를 병합하려면, p의 root의 id를 q의 root의 값으로 수정한다.
위 그림에서 4와 7을 연결시킨다면, 4의 root가 3이고, 7의 root가 5이므로, id[3]의 값을 5로 바꾼다.
quick find에서 너무 많은 원소의 값이 변경되었던 것과 달리, quick union에서는 단 한 원소의 값만 바뀐다.
1 2 3 4 5 6 | public void union(int p, int q) { int i = find(p); int j = find(q); id[i] = j; } |
find query와 union command에 드는 비용을 알아보자.
먼저 find query는 해당 오브젝트의 깊이만큼의 비용이 발생한다.
union command는 find query를 오브젝트 p와 q에 대해 각각 수행하므로 p와 q의 깊이를 합한 것 만큼의 비용이 발생한다.
이 코드는 quick-find에 비교했을 때 for문이 없고(대신 root 메소드에 while문이 있다) 더 간결하다. 하지만, 최악의 경우(tree가 세로로 긴 경우)에는 find의 비용이 너무 크다. 최대 N회의 배열 접근이 필요할 수 있기 때문에, N의 값이 커질 때 사용하기에는 부적절하다.
quick-union에서 초기화/find/union에 드는 비용을 정리하면 다음과 같다.
