반응형
문제
https://www.acmicpc.net/problem/6497
6497번: 전력난
성진이는 한 도시의 시장인데 거지라서 전력난에 끙끙댄다. 그래서 모든 길마다 원래 켜져 있던 가로등 중 일부를 소등하기로 하였다. 길의 가로등을 켜 두면 하루에 길의 미터 수만큼 돈이 들
www.acmicpc.net
풀이
MST를 만드는 알고리즘으로 풀이할 수 있는 문제입니다.
저는 크루스칼 알고리즘을 사용하여 풀이하였고,
단순히 모든 길에 대한 거리를 더한 값에서, MST를 이루는 거리를 빼주는 값이 절약되는 최대 액수입니다.
소스코드
후기
MST를 만드는 방법에 대해 알고있다면 어렵지 않게 풀 수 있는 문제였습니다.
반응형
'PS > 백준' 카테고리의 다른 글
| [BOJ] 백준 15681 트리와 쿼리 (Swift) (0) | 2023.05.23 |
|---|---|
| [BOJ] 백준 17472 다리 만들기 2 (Swift) (0) | 2023.05.18 |
| [BOJ] 백준 1774 우주신과의 교감 (Swift) (0) | 2023.05.18 |
| [BOJ] 백준 4386 별자리 만들기 (Swift) (1) | 2023.05.17 |
| [BOJ] 백준 1197 최소 스패닝 트리 (Swift) (0) | 2023.05.16 |
