백준 6497번 : 전력난, 50% 에서 런타임 에러나는 경우 (python, 파이썬)

1. 문제

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

6497번: 전력난

 

2. 풀이

와 이거 진짜.. input 에서 문제가 있다.

크루스칼만 연습하는거라면 50%까지만 봐도 될 것 같다.

 

50% 에서 런타임에러가 나는 경우를 해결하고 싶으면..

input에 대해 설명을 하자면, < 입력은 여러 개의 테스트 케이스로 구분되어 있다. > 이 부분이 문제가 된다.

우선 테스트 케이스는 다음과 같이 주어졌는데, 쉽게 생각해서 계속 받다가 0,0가 나오면 end flag이구나 생각하게 된다.

7 11
0 1 7
0 3 5
1 2 8
1 3 9
1 4 7
2 4 5
3 4 15
3 5 6
4 5 8
4 6 9
5 6 11
0 0

근데 실제 이 문제에서 내주는 테스트케이스는 이런 식인 것이다.

즉 n,m이 여러번 나올 수 있고 0,0이 나와야 끝난다는 것. 그러니까 while True로 0,0을 잡는 코드를 하나 더 넣어줘야한다. 나머지는 일반 크루스칼과 같으며, 간선을 추가할 때 (정점-1)만 추가한다는 내용을 넣어줘야한다.

7 11
0 1 7
0 3 5
1 2 8
1 3 9
1 4 7
2 4 5
3 4 15
3 5 6
4 5 8
4 6 9
5 6 11
7 11
0 1 7
0 3 5
1 2 8
1 3 9
1 4 7
2 4 5
3 4 15
3 5 6
4 5 8
4 6 9
5 6 11
7 11
0 1 7
0 3 5
1 2 8
1 3 9
1 4 7
2 4 5
3 4 15
3 5 6
4 5 8
4 6 9
5 6 11
0 0

 

 

3. 구현

 

import sys
import heapq
# sys.stdin = open("input.txt")

def find(x, parent):
  if parent[x]==x:
    return x
  else:
    parent[x] = find(parent[x],parent)
    return parent[x]

def uni(x,y,parent):
  x = find(x,parent)
  y = find(y,parent)
  if x==y:
    return
  else:
    parent[y] = x
  return

while True:
  m,n = map(int, sys.stdin.readline().split())
  if (m,n)==(0,0):
    break
  
  edges = []
  parent = [ i for i in range(m+2)]
  total = 0

  while n:
    x,y,z = map(int, sys.stdin.readline().split())
    total+=z
    heapq.heappush(edges, (z,x,y))
    n-=1

  answer = 0
  cnt=0
  while True:
    w,s,e = heapq.heappop(edges)
    if find(s, parent)!=find(e, parent):
      uni(s,e,parent)
      answer+=w
      cnt+=1
    if cnt==m-1:
      break

  print(total-answer)

 

 

참고한 글:

https://jjangsungwon.tistory.com/110

[백준 6497] 전력난 - Python

https://hello70825.tistory.com/92