Advanced Algorithm - MST(Union-Find Algorithm)(2)

* 본 포스팅은 이전 포스팅과 이어지는 내용입니다.

[복습]

• 최소신장트리(MST)의 개념
  - 어떤 그래프를 기반으로 만들어진, 간선의 총 가중치(비용)가 최소이며 사이클 없이 모든 노드가 연결된 트리
  
  
• 최소신장트리의 대표 알고리즘
  - 크루스칼 알고리즘(Kruskal's Algorithm), 프림 알고리즘(Prim's Algorithm)
  
  
• 크루스칼 알고리즘
  - 어떤 그래프를 기반으로 MST를 만들기 위한 알고리즘
  - 모든 간선의 가중치를 오름차순으로 정렬하고 가중치가 낮은 간선부터 사이클이 생기지 않는 조건하에 모든 노드를 연결
  - 사이클의 발생유무를 판단하기 위해서 크루스칼 알고리즘에서는 Union-Find 알고리즘을 사용한다. 
  
  
• Union-Find 알고리즘
  - 크루스칼 알고리즘에서 노드간의 연결을 통해 발생할 수 있는 사이클의 유무를 판단하는 알고리즘
  - 이미 연결된 노드의 집합을 부분집합으로 하여, 기존 부분집합과 새로 이어질 노드(부분집합)의 루트노드를 비교하여 두 부분집합의 루트노드가 다르다면(서로소) 사이클이 발생하지 않는다고 판단(Find)한 후 두 부분집합을 연결(Union)하는 방법 

---

1. Union-Find 알고리즘의 이해(사이클의 발생유무를 검증하는 방법)

a) 사이클이 발생하는 조건

- 먼저, 어떤 조건을 충족해야 사이클이 발생하는지 알아보자. 사이클이 발생하는 조건은 다음과 같다.

1. 그래프의 각 노드는 하나의 집합을 의미한다.
2. 접근경로가 존재하는 노드들은 전체 그래프의 부분집합이자 노드의 합집합으로, 각 노드와 같이 하나의 집합이다.
3. 이미 접근경로가 존재하여 연결된 노드간의 새로운 경로가 생길 때, 사이클이 발생하게 된다.  

- 위의 조건만으로는 이해가 잘 안된다. 예시를 통해 설명하도록 하겠다.(아래 사진참고) 

5단계

- 위의 그림은 크루스칼 알고리즘의 기본 메카니즘 설명을 위해 사용했던 5단계의 그림이다. 

 

- 각 노드 A, B, C, D, E, F, G는 하나의 집합이며, 접근경로에 의해 연결된 노드 A, B, C, D, E, F를 묶어서 하나의 집합으로 판단한다. 

 

- 접근경로에 의해 연결된 노드 A, B, C, D, E, F 사이에 새로운 경로가 생긴다면, 이는 사이클 발생의 3번째 조건인 "이미 접근경로가 존재하여 연결된 노드간의 새로운 경로가 생길 때"의 상황이 되는 것이다.

 

- 그러므로 사이클을 발생시키는 D↔E, D↔B, F↔E, B↔C의 경로를 이용하여 MST를 구성할 수 없다.

 

- 반면에, F↔G 또는 E↔G 경로는 어떠한 노드와도 연결되어 있지 않은 상태이므로 사이클을 발생시키지 않는다. 그러므로 MST를 구성할 수 있는 경로이며 더 낮은 가중치를 갖고 있는 E↔G 경로가 마지막 6단계에서 선택된 것이다. 

 

6단계

- 정리하자면, 사이클은 이미 접근경로를 갖고 있는 노드간 새로운 경로가 생기는 경우 발생하게 되는것이며, 노드간 경로에 중복이 없어야 함을 의미한다. 

 

- 지금까지 설명한 사이클 발생유무의 판별과정을 알고리즘으로 정리한 것이 바로 Union-Find 알고리즘 이다.  

---

2. Union-Find 알고리즘이란?

- Disjoint Set을 표현하기 위해 사용하는 알고리즘으로 트리구조를 활용하는 알고리즘이다.  

- 크루스칼 알고리즘에서 연결된 노드를 찾거나 노드를 서로 합칠 때, 사이클의 발생유무를 판단하기 위한 알고리즘이다.

 

* Disjoint Set이란?

• 서로 중복되지 않는 부분집합들로 나눠진 원소(노드)의 정보를 저장하고 조작하는 자료구조
• 즉, 공통 원소가 없는 서로소 상태의 부분집합에 대한  자료구조를 의미한다. (서로소 집합의 자료구조)

 

a) Union-Find의 연산과정

1) 초기화

- n개의 원소가 개별 집합을 이루도록 초기화한다.

 

 

2) Union(합집합 생성)

- 2개의 개별집합을 하나의 집합으로 합치는 과정으로, 2개의 트리를 하나의 트리로 만든다. 

 

3) Find(서로소 검증 = 사이클 검증)

- 여러 노드가 존재할 때, 2개의 노드를 선택하여 해당 노드가 서로소인지 판별하기 위해 각 그룹의 최상단 노드(루트노드)를 확인하는 과정이다. 즉, 2개의 부분집합이 동일한 부분집합을 갖고 있는지 확인하는 것이다. (루트노드가 달라야 서로소다.)

 

4) Union Find 알고리즘 코드

# find - 부모 노드를 찾는 과정 

def find(x):
   if x == parent[x]: # 원소 자체가 부모인 경우 
      return x
   else:
      p = find(parent[x]) # 재귀함수 - 상위노드를 계속 타고가서 최상위 부모노드를 찾음
      parent[x] = p # 찾은 최상위 부모노드 p를 해당 원소의 부모노드로 설정함
      return parent[x] 
        

# union - 두 개의 노드를 결합하는 과정

def union(x, y):
   x = find(x) # x의 부모노드를 찾고
   y = find(y) # y의 부모노드를 찾고 
   parent[y] = x # x와 y의 부모노드 중 더 상위에 위치한 부모노드로 대체시킴 

 

---

3. Union-Find 알고리즘 - 주의할 점

- Union 과정에서 2개의 부분집합이 합쳐질 때, 어떤 루트노드에 어떤 부분집합이 어떤 방식으로 연결될지 알 수 없다.

- 그러므로 Union 순서에 따라서, 최악의 경우에는 링크드 리스트와 같은 형태의 MST가 생성될 수 있다. 

- 이 경우에는 Find와 Union 함수의 계산량이 O(N)이 될 수 있으므로(루트노드를 찾기위해 모든 노드를 거치는 경우를 의미한다), 이러한 문제를 해결하기 위해 Union-by-rank 또는 path compression 기법을 사용한다. 

 

Union-Find의 최악의 경우

 

a) Union-by-rank 기법

- 각 부분집합인 트리의 높이(rank)를 저장하여 Union 작업을 할 때, 2개의 트리(부분집합)의 높이가 다르면 높이가 작은 트리를 높이가 큰 트리에 연결하는 방식이다. 즉, 높이가 큰 트리의 루트노드가 합쳐졌을 때의 새로운 루트노드가 되게 한다. (아래 사진참고)

 

 

 

- 만약 두 트리의 높이가 동일한 경우, 한쪽 트리의 높이를 1 증가시켜서 나머지 트리를 높이가 증가된 트리에 연결시킨다. (아래 사진참고)

 

 

- 최초의 초기화 시점에서는 모든 원소의 높이가 0인 개별집합이므로, 하나씩 원소를 합치는 과정에서 union-by-rank 기법을 사용한다면 다음과 같은 규칙성을 갖는다. 

• 높이가 h인 트리를 만들기 위해서는, 높이가 h-1인 2개의 트리가 합쳐져야(union) 한다.
  
  
• 높이가 h-1인 트리를 만들기 위해서 최소 n개의 원소가 필요하다면, 높이가 h인 트리를 만들기 위해서는 최소 2n개의 원소를 필요로 한다.
  
  ex) 높이가 1(h-1)인 트리는 최소 2개(n)의 원소를 필요로 한다. 그러므로 높이가 2(h)인 트리를 만들기 위해서는 최소 4개(2n)의 원소가 필요하다. 왜냐면 2개의 원소를 갖고 있는 rank 1짜리 트리 2개를 합쳐야 레벨 2의 트리가 나오기 때문이다. 
  
  
• 따라서 union-by-rank 기법을 사용하면, union 및 find 연산의 시간복잡도는 O(N)이 아닌 O(log N)으로 낮아지게 된다. 즉, 이진트리와 같이 union 연산시 루트노드를 찾을 때 거쳐야 하는 노드의 개수가 절반(50%)으로 줄어든다. 

 

b) Path Compression 기법

- Find 연산을 통해 트리의 루트노드를 찾아서, 루트노드와 자식노드가 한번의 경로로 연결하는 방법(아래 사진참고)

 

- union-by-rank와 path compression 기법을 사용하면 다음과 같은 계산식의 시간복잡도를 만족한다. (아래 사진참고)

 

- 위의 사진에서 설명하는 시간복잡도에 대한 결론은 다음과 같다. N이 무한대에 가까운 값을 가져도, 이는 상수에 가까운 값으로 계산되기 때문에 union-by-rank와 path compression 기법을 사용하면 O(1) 만큼의 시간복잡도를 갖는다.