[백준6497&파이썬] 크루스칼은 최소신장트리를 구할 수 있다.

# 문제

백준 6497 전력난 파이썬 풀이

6497번: 전력난

# 코드

import sys
from heapq import *


# m : 집의 수
# n : 길의 수
def find(p,node) :
  if p[node] == node :
    return node
  p[node] = find(p,p[node])
  return p[node]

def union(p,r,nodeA,nodeB) :
  a = find(p,nodeA)
  b = find(p,nodeB)
  if a==b :
    return

  if r[a] < r[b] :
    p[a] = b
  else :
    p[b] = a
    if r[a] == r[b] :
      r[a] +=1


def solve(m,n) :
  edges = list()
  total = 0
  parent = [i for i in range(m+1)]
  rank = [1] * (m+1)

  for _ in range(n) :
    a,b,c = map(int,sys.stdin.readline().split())
    total += c
    heappush(edges,(c,a,b)) # ( cost, a , b )

  cnt = 0
  while True :
    if cnt == m-1 :
      break
    cost, a, b = heappop(edges)

    if find(parent,a) != find(parent,b) :
      union(parent,rank,a,b)
      total -= cost
      cnt+=1

  print(total)


while True :
  m,n = map(int,sys.stdin.readline().split())
  if m == 0 and n == 0 :
    break
  solve(m,n)

# 풀이

• 크루스칼을 이용하여 MST를 찾는 전형적인 문제이다.
• 출력이 원하는것이 소모하는 전력이 아닌 절약할 수 있는 전력이기 때문에, total에서 MST로 찾은 간선들을 빼주면 절약 가능한 전력이 된다. 원하는 출력조건에 유의하며 문제를 풀면 쉽게 해결 할 수 있었다.