[Python] BOJ / 6497번 / 전력난

6497번: 전력난

---

📝 풀이

• m개의 집(노드)과 n개의 길(간선)으로 구성된 도시(연결 그래프)가 주어지고 해당 도시에서 가로등 일부를 소등하였을 때(일부 간선을 제거하였을 때) 절약할 수 있는 최대 액수를 구하는 프로그램
  • 일부 간선을 제거한 연결 그래프에서 모든 두 노드 쌍은 서로 연결되어 왕래할 수 있어야 한다.
• 전형적인 MST 알고리즘으로 구현할 수 있다.
  • 크루스칼 알고리즘, 최소 힙 자료구조 사용

---

💻 소스코드

import sys

input = sys.stdin.readline

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

def union(a, b):
    a, b = find(a), find(b)
    parent[max(a, b)] = min(a, b)

while True:
    m, n = map(int, input().split())
    if m == 0 and n == 0:
        break

    edges = []
    parent = [i for i in range(m + 1)]
    ans = 0

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

    for edge in edges:
        z, x, y = edge
        if find(x) != find(y):
            union(x, y)
        else:
            ans += z
    
    print(ans)