6497
-
[백준]6479: 전력난 - JAVA문제풀이/백준 2021. 5. 31. 11:36
[백준]6479: 전력난 https://www.acmicpc.net/problem/6497 6497번: 전력난 성진이는 한 도시의 시장인데 거지라서 전력난에 끙끙댄다. 그래서 모든 길마다 원래 켜져 있던 가로등 중 일부를 소등하기로 하였다. 길의 가로등을 켜 두면 하루에 길의 미터 수만큼 돈이 들 www.acmicpc.net 풀이 방향성이 없는 n개의 간선으로 연결된 m개의 노드 중에서 MST를 비용을 찾는 문제이다. MST를 찾아야 하는것은 맞지만 결과로 반환하는 값은 MST값이 아니다. 문제를 읽어보면 결국 최소 비용을 가질 수 있는 불이 켜진 길로만 이동할때 절약할 수 있는 최대 비용을 찾는것이다. 즉, 전체 비용에서 최소비용을 뺀 값이 우리가 구하려고 하는 값이 된다. 그러므로 prim이나 kru..