코딩테스트/Python
[Baekjoon] 6497. 전력난
swwho
2023. 1. 8. 18:24
728x90
반응형
🔗 Problem Link
6497번: 전력난
성진이는 한 도시의 시장인데 거지라서 전력난에 끙끙댄다. 그래서 모든 길마다 원래 켜져 있던 가로등 중 일부를 소등하기로 하였다. 길의 가로등을 켜 두면 하루에 길의 미터 수만큼 돈이 들
www.acmicpc.net
❔Thinking
- 마을과 임의의 두 마을 사이의 거리가 주어질 때, 모든 마을을 연결하는 최소 비용의 가로등 설치 비용을 반환한다.
- 가로등은 두 마을 사이의 거리만큼의 비용이 든다.
💻Solution
import heapq
def find_parent(parent, x):
if parent[x] != x:
parent[x] = find_parent(parent, parent[x])
return parent[x]
def union_parent(parent, a, b):
a = find_parent(parent, a)
b = find_parent(parent, b)
parent[max(a,b)] = min(a,b)
while True:
n, m = map(int, input().split())
if n == 0 and m == 0:
break
parent = [i for i in range(n+1)]
total_cost = 0
result = 0
q = []
for _ in range(m):
x, y, z = map(int, input().split())
total_cost += z
heapq.heappush(q, (z, x, y))
while q:
cost, a, b = heapq.heappop(q)
if find_parent(parent, a) != find_parent(parent, b):
union_parent(parent, a, b)
result += cost
print(total_cost - result)
🗝️keypoint
- 크루스칼 알고리즘을 통해 최소 비용으로 모든 마을을 연결하는 그래프를 완성한다.
- 절약한 비용은 모든 마을의 가로등 비용에서 마을을 연결하는 최소 비용을 제하여 구할 수 있다.