[자료구조] Union find & an Application

• 본 게시글은 대학생이 수업을 듣고 내용을 정리한 것입니다.
• 따라서 완벽하지 않은 부분이 있을 수 있습니다.
• 아울러 본 게시글에 포함된 코드들은 대략적인 개념 이해만을 위해 작성된 것으로 완전하지 않은 코드임을 알려드립니다.

---

Minimum Sparsing Tree

• 주어진 그래프에서 엣지들의 subset을 찾고 그 결과로 엣지 cost의 합이 최소인 '연결된' 그래프를 찾아라.
• 해당 그래프는 자연스럽게 트리가 된다. 이는 사이클이 없다. 싸이클이 있다고 가정하면 '엣지 cost 합 최소' 조건이 성립이 안되기 대문이다. 엣지는 '노드개수 - 1'일 것이다.
• 해당 질문에 대한 답은 그래프 형태에 따라 여러개일 수 있다. (유일하다는 것을 증명하기 위해서는 edge weight가 모두 다름을 증명하면 된다.)

---

Kruskal Algorithm

• 1) 엣지를 확인하여 작은 것부터 추가시킨다.
• 2) 사이클이 생기면 해당 엣지는 skip한다.
• 3) 엣지가 '노드개수 - 1'이 될 때까지 반복한다.
• 즉, '싸이클을 만들지 않는 가장 작은 cost를 가지는 엣지'를 추가한다.
• 직관적으로 싸이클을 만드는 엣지를 그냥 추가하고 그 전의 더 작은 cost를 가지는 엣지를 빼면 '최소'에 대한 성립이 안될 것으로 예상된다. (직관적 증명)
• cost(weight)를 통해 엣지를 구분해야 하는가? / 엣지를 어떻게 표현할 것인가? 와 같은 질문이 생긴다.
• 엣지 표현 : (a,b,w), a와 b는 연결된 노드, w는 엣지의 weight
• 추가된 노드로 연결된 그룹을 '덩어리'라고 했을 때 같은 덩어리에 있는 노드끼리 연결되면 싸이클이 발생한다.
• 이러한 '덩어리' 체크를 빠르게 할 필요가 있다. DFS로 이를 확인할 수 있다. O(N)의 시간이 소요된다.
• Kruskal 알고리즘은 O(MN)? 더 빨라질 수 있다.

---

Union & Find, Disjoint set

• n개의 item이 존재한다고 했을 때 초기엔 n개의 그룹 모두가 각각의 item으로 구성된다.
• Union(a,b) : a,b 각 그룹을 join한다.
• Find(a) : a가 속한 그룹의 id를 리턴한다. (a,b의 공통 그룹여부를 판단하는데 활용)
• 구조 : 각 item은 노드이고, 시작시엔 각각 하나의 노드를 가진 Tree가 구성된다. Union Operation을 진행하면 각 Tree는 하나의 그룹이 되고, root가 해당 group의 id가 된다. 각 노드는 parent로의 point만 보유한다. 즉, child는 찾을 수 없는 구조이다.
• 성능 : Find는 최악의 경우 O(N)의 시간이 걸린다. Union도 각 노드의 그룹 여부를 체크하고 join해야하므로 Find 과정을 필요로 한다. 따라서 Find가 빨라야 한다. Find하기 좋은 form은 한 개의 root에 모든 노드가 붙어있는 형태겠지만 이를 union하면서 유지하기는 어려운 일이다. 두 트리의 root 노드 중 하나를 남은 root 노드의 아래로 속하도록 하는 것이 적합하다. 어쨌든 이러한 고민을 통해 Height가 조절되어 FInd는 O(logN)보다 빠른 성능을 보인다.
• 두 트리의 root 노드 중 어떤 root 노드가 아래로 속하도록 할 것인지는 자식갯수 혹은 깊이를 고려한다. 이것이 합리적임은 직관적으로 알 수 있는데, 이를 '휴리스틱(직관)'이라고 한다. 자식갯수 혹은 깊이 중 어떤 휴리스틱을 사용하든지 O(logN) 이하의 Height가 보장된다.

---

Path Compression

• Path Compression : 깊이가 깊은 자식들의 Parent로의 포인터를 모두 root로 이동한다. 이런 방식이 메모리 소모가 많다면 2단계 root가 아닌 2단계 위의 Parent로 포인터를 이동한다.
• Valiant's Proof : 이러한 방식으로 각 operation이 amortized time(균등분할시간)으로 O(logN), O(log*N), O(a(N))의 시간복잡도를 가질 수 있음을 증명했다. 증명과정은 매우 어렵다. (교수님도 잘 모름)