MST - 이론

코딩 테스트 시 필요한 이유

코딩 테스트에서 가장 많이 나오는 문제 유형이 문자열 처리 유형이라고 한다면 가장 어려운 문제를 꼽으라면 그래프 문제를 뽑을 것 같다.

 

Trie를 활용하여 풀어야 하는 문제가 아닐 경우 문자열  처리 문제는 대부분 Lv3 정도의 문제에 속하지만 그래프는 Lv3 ~ Lv4 널리 퍼져있고 문제 난이도 자체도 꽤 어려운 편이라고 할 수 있다.

 

그래프 문제 같은 경우 종이의 사용이 한정되어 있는 코딩 테스트의 경우 상황을 상상하기가 힘들고 대부분의 그래프 문제의 해결 방법은 Brute Force 방식인 경우가 많아 난이도가 증가한다고 생각한다.

그래프는 이 Brute Force 방식을 얼마나 효율적으로 수행하는지가 중요해지고 이 때문에 이미 수많은 알고리즘이 존재하며 이를 모를 경우 문제 해결에 대한 아이디어를 떠올리기조차 어려워진다고 생각한다.

(정렬 알고리즘은 Brute Force 방식에 해당하고 이 때문에 정렬 관련 알고리즘이 많은 것과 유사하다고 생각한다)

 

Tree나 DFS, BFS는 많은 문제를 풀어보았기 때문에 자면서도 할 수 있을 정도로 많이 구현해 봤으므로 딱히 정리가 필요 없지만 MST는 자주 나오는 문제 유형이 아니었기 때문에 MST 알고리즘에 대해서는 잘 알지 못했다.

 

따라서 MST에 대한 이론 및 구현 방법을 2번에 나눠 정리함으로써 코딩 테스트에서 사용할 수 있게 하기 위해 정리를 했다.

---

Spanning Tree

◎ Spanning Tree란?

Spanning Tree를 한글 말로 하면 "신장 트리"라고 한다.

이 "신장"이라는 의미가 약간 모호하다고 생각해 "Spanning Tree"라는 단어 자체를 해석해서 의미를 알아보려 한다.

 

Span을 직역하면 "널리 걸치다"라는 의미를 가지고 있다. 그래프에서 "널리 걸치다"라는 것은 "널리 연결되어 있다"라는 의미와 유사할 것이다.

결국 Spanning Tree는 "널리 연결되어 있는 Tree"라는 의미로 "그래프 내의 모든 정점이 연결되어 있는 Tree"라고 해석할 수있을 것이다.

 

Tree의 여러 가지 성질 중 "N개의 정점을 가진 Tree는 (N-1) 개의 Edge를 가진다"라는 특성이 있었다.

즉 Spanning Tree 또한 (N-1) 개의 Edge를 가짐을 알 수 있다.

 

◎ Spanning Tree 특징

하나의 그래프에는 수많은 신장 트리가 존재한다.

N개의 정점이 모두 연결되어 있다고 가정하고 이 때 Spanning Tree의 개수를 생각해 본다면 (N-1)!이라는 것을 쉽게 유추할 수 있다.
(이유 : 첫번째 정점에서 이동할 수 있는 정점 N-1 * 이전에 선택된 정점에서 선택할 수 있는 정점 N-2 *.....)

 

즉, 하나의 그래프에는 수많은 ST가 존재함을 유추할 수 있다.

 

모든 정점들이 연결되어 있고 사이클을 포함해서는 안된다.

"모든 정점들이 연결되어 있다"라는 것은 ST의 정의에서 명시된 조건이다.

 

또한 사이클을 포함하지 않는다는 것은 Tree의 정의이자 특성이므로 당연히 Tree의 일종인 Spanning Tree 또한 가져야 할 속성이다.

 

(n-1) 개의 간선으로 되어있다.

N개의 정점을 가진 Tree가 (N-1) 개의 Edge를 가지는 것 또한 Tree의 성질이다.

---

MST

◎ MST란?

ST(Spanning Tree)에 Minimum(M)이 붙은 것이 MST이다.

최소 Spanning Tree? 이게 무슨 의미일까?

 

ST는 현실에서도 많이 활용할 수 있는 알고리즘인데 N개의 Node를 모두 연결해야 할 경우 최소 비용으로 연결하기 위해 (N-1) 개의 선을 사용하는 것이 가장 좋기 때문이다.

문제는 Node 사이 모든 비용이 동일하다면 좋겠지만 현실은 그렇게 만만하지 않다는 것이다.

 

예를 들어 "서울 - 대구 - 부산"을 연결하는 도로를 만든다고 생각해 보자.

평범한 사람들은 "서울 - 대구" 도로를 짓고 "대구 - 부산"도로를 지으면 3개 도시가 연결되겠다고 빠르게 파악할 수 있다.

하지만 단순 ST 로직으로 컴퓨터가 도로를 연결한다면 "서울 - 부산" 도로와 "서울 - 대구" 도로를 지어버릴 수도 있는 것이다.

이 경우 부산에서 대구를 가려면 부산 → 서울 → 대구를 가야 하는 대장정이 벌어지는 것이다.

 

이 때문에 간선에 가중치가 존재하는 그래프에서 "최소 비용으로" ST를 만드는 알고리즘이 필요해졌고, 이것이 바로 MST이다.

 

◎ MST 구현 알고리즘

Kruskal MST

Greedy Algorithm을 활용하여 MST를 구하는 방법이다.

 

ST의 "사이클을 포함하지 않음"이라는 조건과 "최소 비용의 간선이어야 됨"이라는 조건을 사용하는 것으로써 이전 단계에서 만들어진 ST와는 관계없이 무조건 최소 가중치를 가진 Edge(간선)만 선택하는 Edge 선택 기반 알고리즘이다.

 

만드는 과정은 아래와 같다.

1. 그래프의 간선들을 가중치의 오름차순으로 정렬한다.
2. 정렬된 리스트에서 순서대로 간선을 선택하는데 사이클을 형성하지 않도록 선택한다.
   • 즉, 낮은 가중치의 Edge부터 순서대로 선택하되 사이클을 형성하지는 않게 선택
3. 2번에 선택한 간선을 MST의 집합에 추가하고 다시 2번 수행

 

Prim MST

임의로 지정한 시작 정점에서 출발하여 신장트리를 단계적으로 이어가는 방법이다.

 

Kruskal이 Edge 선택 기반의 알고리즘이라면 Prim MST는 정점을 확장시켜나가는 방식으로 Node 선택 기반의 알고리즘으로써 이전 단계에서 만들어진 신장 트리를 계속해서 활용한다.

 

만드는 과정은 아래와 같다.

1. 시작 정점을 MST 집합에 포함한다.
2. MST 집합에 포함되어 있는 정점들을 A, MST 집합에 포함되어 있지 않은 정점들의 집합을 B라고 할 때 A와 B를 연결시키는 Edge 중 최소 가중치를 찾고 그 간선의 양 정점을 A에 포함시킨다.
3. MST 집합이 N개의 정점을 포함하거나 Tree가 (N-1) 개의 간선을 가질 때까지 2번 과정을 반복

위 2개 알고리즘의 시간 복잡도는 다음 Section에서 직접 코드로 구현해 보며 알아보도록 하자.