BaekJoon 6497번 : 전력난 (python)

BaekJoon 6497번 : 전력난 (G4 34.396%)

전력난 문제

크루스칼 알고리즘을 이용한 MST문제이다.

• 해당 문제는 연결된 그래프들 중에서 불필요하게 긴 간선들을 제거해 최소한의 전선만 남겨서 효율적인 가중치로 만들어야 하는 문제이다.
• 이를 반대로 생각해서 크루스칼 알고리즘과 같이 가중치가 낮은 노드들끼리 먼저 연결시켜줌으로 써 총 전력에서 연결된 노드들의 가중치를 제외해서 절약할 수 있는 최대 비용을 얻어낼 수 있다.

---

import sys
input = sys.stdin.readline

def find(x) :
    if root[x] != x:
        root[x] = find(root[x])
    return root[x]

def union(x,y) :
    rootX = find(x)
    rootY = find(y)

    if rootX < rootY :
        root[rootY] = rootX
    else :
        root[rootX] = rootY

while True :
    global root
    n, m = map(int,input().split())
    if n == m == 0 :
        break
    root = list(i for i in range(n+1))
    edges = list()

    result = 0
    for _ in range(m) :
        a, b, cost = map(int,input().split())
        edges.append((cost,a,b))
        result += cost
    edges.sort()

    for i in edges :
        cost, x, y = i[0], i[1], i[2]
        
        if find(x) != find(y) :
            union(x,y)
            result -= cost
    print(result)

---