08_03 [연습문제] 최소 신장 트리 구하기

01 당장 좋은 것만 선택하는 그리디

02 아이디어를 코드로 바꾸는 구현

03 꼭 필요한 자료구조 탐색 알고리즘 DFS/BFS

04 기준에 따라 데이터를 정렬

05 범위를 반씩 좁혀가는 탐색

06 다이나믹 프로그래밍

07 가장 빠른 길 찾기

08 다양한 그래프 알고리즘

[문제]

하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 신장 트리라고 한다.

다음의 그래프의 최소 신장 트리를 구하시오.

입력예시

7 9
1 2 29
1 5 75
2 3 35
2 6 34
3 4 7
4 6 23
4 7 13
5 6 53
6 7 25

출력예시

159