[최단경로] 모든 지점을 연결하는 길의 최소 길이 ( Minimun Spanning Tree )

예제) 모든 도시를 오갈 수 있는 고속도로를 건설하려고 할 때, 총 고속도로 길이의 최소값을 구하라. 

 

 

 

복잡하다. 써클(Circle)이 보이도록 만들어보자. 써클이란, 지점들이 서로 연결되어 순환하는 구조를 말한다. 

 

 

 

 

최소길이의 고속도로를 만들려면 고속도로가 최소 개수여야 한다. n개의 지점이 있으면 n-1개의 길만 있으면 된다. 이를 최소신장트리(Spanning Tree)라고 한다. 최소신장트리를 만들려면 순환구조를 없애야 한다. 최대길이의 간선을 제거하여 총 길이가 최소 길이인 스패닝트리를 만드는 것이 목적이다. 

 

1) D - F - E 써클

 

 

D와 F를 잇는 간선이 12km로 가장 길다. 고로 제거한다. 

 

총 제거 길이 : 12

 

2) D - A - F - E 써클

 

 

D-F를 제거했더니 또 다른 써클이 생성되었다. D-E 간선이 가장 길다. 제거한다. 

 

총 제거 길이 : 12 + 11

 

3) D - C - B - E - F - A 써클

 

 

D-E 간선을 제거했더니 또 다른 써클이 나왔다. 가장 긴 C-B 간선을 제거한다. 

 

총 제거 길이 : 12 + 11 + 10

 

 

4) 최소신장트리 완성

 

 

 

총 노드 개수 : 6개

총 간선 개수 : 5개

총 제거 길이 : 12 + 11 + 10 = 33

총 고속도로 길이 : 60

 

총 최소 고속도로 길이 : 60 - 33 = 27

 

써클마다 가장 긴 간선을 Greedy하게 제거하는 루틴을 반복하여 최소신장트리를 만드는 알고리즘을 Kruskal MST 알고리즘이라 한다. 

 

 

---

 

 

참고자료

2021년 7기 모집대비 SSAFY(삼성 청년 SW아카데미) SW적성진단 5일 완성