[Python] 백준 6497번 : 전력난

https://www.acmicpc.net/problem/6497

6497번: 전력난

---

💡 문제 풀이

최소 신장 트리 (MST)에 관한 문제이다.

 

크루스칼 알고리즘을 이용해서 해결했다.

잘 읽어봐야하는 점은 문제에서 출력해야 하는 값은 최소 신장 트리의 비용이 아닌, 가로등의 불을 끔으로써 아낀 비용을 출력해야한다.

✔️ 느낀 점

문제가 요구하는 점을 제대로 안 읽어서 틀렸을 때 너무나도 당황했다.

💻 코드

import sys
input = sys.stdin.readline

def find(x):
    if x != parent[x]:
        parent[x] = find(parent[x])
    return parent[x]
    
def union(x, y):
    x = find(x)
    y = find(y)
    
    parent[y] = x
    
while True:
    M, N = map(int, input().split())
    if M == 0 and N == 0: break
    
    parent = list(range(M))

    graph = []
    for i in range(N):
        start, end, cost = map(int, input().split())
        graph.append([start, end, cost])
    graph.sort(key=lambda x:x[2])

    savedCost = 0
    for edge in graph:
        if find(edge[0]) != find(edge[1]): union(edge[0], edge[1])
        else: savedCost += edge[2]
            
    print(savedCost)