[백준] 6497번 전력난 ★

💡문제접근

• 길의 가로등을 켜 두면 하루에 길이 미터 수만큼의 돈이 들어간다. 일부를 소등하여 그만큼의 돈을 절약할 수 있다.
• 절약할 수 있는 최대 비용을 구하라는 것은 결국 최소 신장 트리에 포함되지 않는 간선의 가중치의 합을 구하라는 문제와 동일하다.

💡코드(메모리 : 65368KB, 시간 : 2556ms)

import sys
input = sys.stdin.readline

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)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b

while True:
    m, n = map(int, input().strip().split())
    parent = [0] * (m+1)
    edges = []
    result = 0
    if m == 0 and n == 0:
        break

    for i in range(1, m+1):
        parent[i] = i

    for _ in range(n):
        x, y, z = map(int, input().strip().split())
        edges.append([z, x, y])
    edges.sort()

    for edge in edges:
        cost, x, y = edge
        if find_parent(parent, x) != find_parent(parent, y):
            union_parent(parent, x, y)
        else:
            result += cost
    print(result)

💡소요시간 : 48m