6497 - 전력난

info

• 문제 보기: 6497 - 전력난
• 소요 시간: 23분 34초
• 풀이 언어: python
• 체감 난이도: 2️⃣
• 리뷰 횟수: ✅

풀이 키워드

스포주의

그래프 최소스패닝트리 유니온파인드

풀이 코드

info

• 메모리: 61004 KB
• 시간: 1852 ms

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

parent = []
def union(a, b):
    global parent
    
    pa = find(a)
    pb = find(b)
    
    if pa < pb:
        parent[pb] = pa
    else:
        parent[pa] = pb


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


def solution():
    global parent
    
    while True:
        m, n = map(int, input().split())
        if m == n == 0: break
        
        parent = [i for i in range(m)]
        tree = []
        zsum = 0
        for _ in range(n):
            x, y, z = map(int, input().split())
            zsum += z
            tree.append((z, x, y))
            
        # Kruskal
        mst_value = 0
        tree.sort()
        
        for data in tree:
            weight, a, b = data
            if find(a) != find(b):
                mst_value += weight
                union(a, b)
        
        print(zsum - mst_value)


if __name__ == '__main__':
    solution()

풀이 해설

MST 문제이므로, 크루스칼 알고리즘을 사용하면 된다.

Kruskal 알고리즘의 설명은
최소 스패닝 트리 풀이 내용으로 대체한다.

다만 절약 비용을 구하는 문제이므로, mst_value로 MST 간선 총합을 구한 뒤,

모든 z값의 합에서 이를 빼야 한다.

메모

• 금방 풀었는데 입력받는 방식이 달라서 WA 고치느라 시간 더 먹음
  • TC 여러개 주어지고 TC 개수 대신 EOF 플래그가 0 0으로 주어진다는 소리였음 🙁

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

--> 따라서 위와 같이 수정해야 AC를 받을 수 있다.