풀이.
최소 신장 트리 알고리즘인 크루스칼 알고리즘을 이용해서 풀면된다.
최소 비용을 구해야하는 문제이니 cost를 기준으로 graph를 정렬 시킨 후
크루스칼 알고리즘을 이용하면 어렵지 않게 풀 수 있다.
최소 신장 트리 알고리즘이 가물가물해서 한번 풀어봤다.
소스코드.
<script src="https://gist.github.com/hanhyung6376/f6622fd34ba8c968bc12afce179c4d80.js"></script>
'프로그래밍 > 백준' 카테고리의 다른 글
| [백준] 11724. 연결 요소의 개수 - 파이썬 (0) | 2021.10.09 |
|---|---|
| [백준] 17435. 합성함수와 쿼리 (0) | 2021.10.05 |
| [백준] 18352. 특정 거리의 도시 찾기 - 파이썬 (0) | 2021.09.27 |
| [백준] 16975. 수열과 쿼리 21 - 파이썬 (0) | 2021.09.25 |
| [백준] 1238. 파티 - 파이썬 (0) | 2021.09.24 |
