[Python] 백준 - 6497 전력난

백준 - 6497 전력난

문제

성진이는 한 도시의 시장인데 거지라서 전력난에 끙끙댄다. 그래서 모든 길마다 원래 켜져 있던 가로등 중 일부를 소등하기로 하였다. 길의 가로등을 켜 두면 하루에 길의 미터 수만큼 돈이 들어가는데, 일부를 소등하여 그만큼의 돈을 절약할 수 있다.

 

그러나 만약 어떤 두 집을 왕래할 때, 불이 켜져 있지 않은 길을 반드시 지나야 한다면 위험하다. 그래서 도시에 있는 모든 두 집 쌍에 대해, 불이 켜진 길만으로 서로를 왕래할 수 있어야 한다.

 

위 조건을 지키면서 절약할 수 있는 최대 액수를 구하시오.

입력

입력은 여러 개의 테스트 케이스로 구분되어 있다.

각 테스트 케이스의 첫째 줄에는 집의 수 m과 길의 수 n이 주어진다. (1 ≤ m ≤ 200000, m-1 ≤ n ≤ 200000)

 

이어서 n개의 줄에 각 길에 대한 정보 x, y, z가 주어지는데, 이는 x번 집과 y번 집 사이에 양방향 도로가 있으며 그 거리가 z미터라는 뜻이다. (0 ≤ x, y < m, x ≠ y)

 

도시는 항상 연결 그래프의 형태이고(즉, 어떤 두 집을 골라도 서로 왕래할 수 있는 경로가 있다), 도시상의 모든 길의 거리 합은 231미터보다 작다.

 

입력의 끝에서는 첫 줄에 0이 2개 주어진다.

출력

각 테스트 케이스마다 한 줄에 걸쳐 절약할 수 있는 최대 비용을 출력한다.

 

 

문제해결방법 - 

 

1. 유니온 파인드(Union Find)와 프림(Prim) 알고리즘으로 구현할 수 있다.

2. 총 가로등을 유지하는 비용에서 위 방법으로 모든 도시들을 방문하는 최소 비용(점등된 도시만을 방문하는 최소비용)을 빼준다.

 

-코드

- 유니온 파인드(Union Find)

import sys
import heapq
import math
input = sys.stdin.readline

def FIND(x):
	if parent[x] != x:
		parent[x] = FIND(parent[x])
	return parent[x]

def UNION(x, y):
	x = FIND(x)
	y = FIND(y)
	if x < y:
		parent[y] = x
	else:
		parent[x] = y

while True:
	m, n = map(int, input().split())
	if m == 0 and n == 0:
		break
	d, parent = [0], [i for i in range(m+1)]
	edge, ans = [], 0
	sum_cost = 0
	for _ in range(n):
		a, b, cost = map(int, input().split())
		sum_cost += cost
		edge.append((a, b, cost))
	edge.sort(key = lambda x : x[2])
	for idx in edge:
		a, b, cost = idx
		if FIND(a) != FIND(b):
			ans += cost
		UNION(a, b)
	print(sum_cost-ans)

 

- 프림(Prim)

import sys
import heapq
import math
input = sys.stdin.readline

def prim(idx):
	q = []
	heapq.heappush(q, (0, idx))
	ans, cnt = 0, 0
	while q:
		cost, idx = heapq.heappop(q)
		if v[idx] == 1:
			continue
		v[idx] = 1
		ans += cost
		cnt += 1
		for next, c in graph[idx]:
			if v[next] == 0:
				heapq.heappush(q, (c, next))
	return ans

while True:
	m, n = map(int, input().split())
	if m == 0 and n == 0:
		break
	graph = [[] for _ in range(m+1)]
	v = [0 for _ in range(m+1)]
	sum_cost = 0
	for _ in range(n):
		a, b, cost = map(int, input().split())
		graph[a].append((b, cost))
		graph[b].append((a, cost))
		sum_cost += cost
	print(sum_cost-prim(0))