[Python] G4_6497_전력난 ⚡

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초
• 메모리 제한: 256MB

코드

import sys
input = sys.stdin.readline

# Union Find
def find(x):
    if parent[x] == x:
        return x
    return find(parent[x])

def union(a,b):
    a = find(a)
    b = find(b)
    
    if a < b:
        parent[b] = a
    else:
        parent[a] = b
        
# Input
while True:
    N,M = map(int,input().split())
    if N == 0 and M == 0: exit(0)
    
    paths = []
    all_spend = 0 # 모든 비용의 합
    for _ in range(M):
        a,b,w = map(int,input().split())
        paths.append((a,b,w))
        all_spend += w
    paths.sort(key = lambda x : x[2])
    parent = list(range(N+1))

    # Kruskal Algorithm
    spend = 0 # 최소 비용
    cnt = 0   # 간선의 개수
    for a,b,w in paths:
        if find(a) != find(b):
            union(a,b)
            spend += w
            cnt += 1
            
        if cnt == N-1:
            break

    # Output
    print(all_spend - spend)

1. Union Find와 Kruskal Algorithm으로 쉽게 풀 수 있는 문제이다.

2. 하지만 다른 점은, 최소 비용을 출력하는 것이 아니라 절약한 비용을 출력해주어야 한다.

• 이를 위해서 입력시에 모든 비용을 all_spend에 넣어준다.

• all_spend += w

3. Kruskal Algorithm으로 최소 비용 spend를 구한다.

4. 최종적으로 모든 비용 all_spend - 최소 비용 spend, 즉 절약한 비용을 출력해준다.

• print(all_spend - spend)

느낀 점 & 배운 점

1. 처음에는 기존과 똑같이 코드를 작성했다가 답이 다르게 나와서 혼란스러웠지만, 쉽게 해결할 수 있는 문제였다.

2. 정석적인 문제는 앞으로도 잘 나오지 않을 것이기에, 문제에서 조금씩 변형한 점을 잘 캐치 후 적용하여 코드를 작성하는 것이 중요할 것 같다!