나동빈님의 '이것이 코딩테스트다 with 파이썬'저서와 유튜브 강의를 참고하며 작성하였습니다. 코드 출처: https://github.com/ndb796/python-for-coding-test ▶ 신장트리란? 그래프에서 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 의미한다. 모든 노드는 연결하기위해 모든 간선을 사용하지 않아도 된다는 점에서 모든 노드들이 연결되어있지만 최소한의 비용으로 구성되는 신장 트리를 찾아야할 때 효율적으로 사용될 수 있다. > 시간복잡도: 해당 알고리즘에서 가장 많은 시간을 요하는 곳이 간선의 정렬을 수행하는 부분으로 간선 개수가 E개 일때 O(ElogE)의 시간복잡도를 가진다. ▶ 동작과정 step 1. 간선 비용을 오름차순으로 정렬하여 최소 비용의 간선부터 ..