[최소 신장 트리 MST(Minimum Spanning Tree)] 최소 비용으로 정점 연결시키기

 

▶ 신장 트리(Spanning Tree)

 그래프 내에 있는 모든 정점이 연결되어 있고 사이클이 없는 그래프

n개의 정점이 있다면 신장 트리의 간선 수는 n-1개가 된다

 

▶ 최소 신장 트리 (Minimum Spanning Tree)

각 간선이 가지고 있는 가중치의 합이 최소가 되는 신장 트리 (가중치는 거리, 비용, 시간 등이 될 수 있다)

 

즉, 최소 신장 트리는 정점과 간선이 주어졌을 때, 최소 비용으로 정점들을 연결시키는 방법을 찾는 것이다. 이런 유형의 문제를 풀기 위해서는 프림 알고리즘(Prim’s Algorithm) 이나 크루스칼 알고리즘(Kruskal’s Algorithm) 을 사용해야한다. 사이클의 존재 유무를 확인할 때는 이전에 배웠던 유니온 find 방법을 이용하면 된다.

---

Ex) A, B, C, D, E  섬이 있는데, 섬끼리 다리를 건설하기로 했습니다. 그리고, 각각의 다리를 건설하는데는 위와 같은 비용이 듭니다.  모든 섬을 다 연결하고자 합니다. 다리를 건설하는데 든 최소 비용은 얼마일까요? 

 

 

=> 크루스칼 알고리즘과 Union Find 방법을 사용해서 풀어주세요