난이도 : 골드 4
유형 : MST
출처 : https://www.acmicpc.net/problem/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 을 먼저 분석해보면
7 11 # 집의 수 7, 길의 수 11
0 1 7 # 이어서 11개의 줄에 각 길에 대한 정보, x,y,z x번과 y번 집 사이에 거리 z
0 3 5
1 2 8
1 3 9
1 4 7
2 4 5
3 4 15
3 5 6
4 5 8
4 6 9
5 6 11
0 0 # 11개의 길의 정보 이후에 마무리 0 0 입력그래서 우리가 뭘 해야 하나면 이 연결 그래프의 형태인 도시에 연결되어 있는 길(간선) 들을 제거할건데 두가지 조건에 입각해 제거할 것이다.
- 길이 제거 되어도 연결그래프 일 것,
- 가장 효율적으로 제거할 것
=> 즉 최소 신장 트리를 만들면 된다.
이때 제거했을 때의 값을 출력해주면 답이 될 것이다.
제거할때의 값의 합은
제거한 값 = 모든 간선 가중치 합 - MST 가중치 합 을 해주면 된다.
해답 및 풀이
import sys
input = sys.stdin.readline
# 유니온 파인드 함수 정의
def find(x):
if parent[x] != x:
parent[x] = find(parent[x])
return parent[x]
def union(a,b):
ra, rb = find(a), find(b)
if ra == rb:
return False
if rank[ra] > rank[rb]:
parent[rb] = ra
elif rank[ra] < rank[rb]:
parent[ra] = rb
else:
parent[rb] = ra
rank[ra] += 1
return True
while True: # 0 0 입력이 나올때 까지 테스트 케이스 반복
m, n = map(int,input().split()) # m : 노드 n : 간선
if m == 0 and n == 0:
break
edges = []
for _ in range(n):
x, y, z = map(int,input().split())
# x, y, z 로 입력받았지만 append 해줄 때는 가중치를 제일 먼저
# => sort 할때 가중치 순대로 하려고
edges.append((z,x,y))
parent = [i for i in range(m)] # 초기 parent 배열은 자기자신을 부모로 가진다.
rank = [0] * m # 노드 수 대로 0으로 초기화
# 크루스칼
edges.sort()
mst_weight = 0
picked = 0
# 모든 간선 가중치 합
total = 0
for w, u, v in edges:
total += w
for w, u, v in edges:
if union(u, v):
mst_weight += w
picked += 1
if picked == n -1 :
break
print(total - mst_weight) # 절약한 간선의 가중치 = 전체 가중치 - mst 가중치