BOJ 6497 전력난(Python 3)

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

간단한 MST 문제이다.

돈이 가장 많이 드는 방법은 가로등을 전부 켜는 것

돈이 가장 적게 드는 방법은 MST를 이용하는 것

둘의 차를 출력하면 끝

입력의 끝에서 0 0에 나오므로 while문을 이용해 풀어야 한다.

질문 글에 나와 같은 사람이 있어서 다행이었다.

없었으면 맞왜틀 외치면서 내가 질문 글을 썼을 듯

Python3, Pypy3 둘다 sys.stdin.readline 을 써야하며, Python3은 재귀함수 깊이를 따로 설정해주지 않으면 런타임 에러가 난다.

그리고 cnt라는 변수를 이용해 cnt=n-1이 되면 for문을 빠져나오게 만들어야 한다. 안그러면 시간 초과가 나온다.

코드 확인

import sys
sys.setrecursionlimit(1000000)
input=__import__('sys').stdin.readline
 
def Find(x):
    if S[x]<0:return x
    S[x]=Find(S[x])
    return S[x]
def Merge(x,y):
    x,y=Find(x),Find(y)
    S[x]=y
 
while 1:
    m,n=map(int,input().split())
    if m==n==0:break
    S=[-1]*n
    D=[];ans=0;cnt=0
    for i in range(n):
        a,b,c=map(int,input().split())
        D.append([c,a,b])
    D.sort()
    for i in range(len(D)): ans+=D[i][0]
    for i in range(len(D)):
        if Find(D[i][1])!=Find(D[i][2]):
            Merge(D[i][1],D[i][2])
            ans-=D[i][0]
            if cnt==n-1:break
    print(ans)