최소 비용 신장 트리(Minimum Spanning Tree, MST)는연결된 가중 그래프에서 모든 정점을 포함하고, 간선의 총 가중치가 최소인 트리를 의미합니다. 예를 들어, 아주 큰 놀이터를 설계하고 있다고 생각해봅시다. 이 놀이터에는 여러 개의 놀이기구가 있는데, 이 놀이기구들을 "모두 연결하는 길"을 만들어야 합니다. 길을 만들 때는 "비용"이 드니까, 가능한 "적은 비용"으로 모든 놀이기구를 연결하는 것이 목표입니다. 어떻게 하면 좋을까요? 놀이기구는 점으로 생각하고, 길은 선으로 생각해봅시다. 모든 놀이기구를 연결하는 선을 그려야 해요. 그리고 가장 적은 비용으로 모든 놀이기구를 연결해야 해요. 즉, 길의 총 길이가 최소가 되도록 해야 하는 거죠. 길을 만들 때, 같은 곳을 두 번 이상 돌아오..
