[백준 6497번] 전력난 문제 풀이 (with Python)

< 문제 >

 

 

 

 

< 입출력 >

 

 

< 풀이 >

 

절약할 수 있는 최대 비용의 값은 (모든 길을 연결했을 때의 비용) - (왕래할 수 있는 경로가 있는 경우의 최소 비용)을 빼면된다.

따라서, 루트 노드를 비교해 루트노드가 다르면 연결한 후, 비용을 더해 result 값에 더해주면 (왕래할 수 있는 경로가 있는 경우의 최소 비용)이 된다.

z값을 모두 더한값에서 위의 값을 빼주면 된다!

 

 

 

< 코드 > 

import sys
input = sys.stdin.readline

def find(x):   # 루트 노드 찾는 함수
    if x == parent[x]:
        return x
    else:
        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
    parent = [i for i in range(M)]
    arr = []
    result = 0
    before_cost = 0

    for _ in range(N):
        x, y, z = map(int, input().split())
        arr.append((x, y, z))

    arr.sort(key=lambda x : x[2])

    for x, y, z in arr:
        before_cost += z
        if find(x) != find(y):
            union(x, y)
            result += z

    print(before_cost - result)