1197번 - 최소 스패닝 트리
입력의 끝이 꼭 개행문자일 필요는 없습니다. [:-1] 없이 바로 split을 해도 맨 끝의 공백을 무시하고 나눌 수 있습니다.
개행문자가 있으면 "1 2 3\n"에 [:-1]을 했을 때 "1 2 3"이 되고, 이것을 split해서 리스트로 저장할 수 있습니다. 하지만 개행문자가 없으면 "1 2 3"에 [:-1]을 해서 "1 2 "가 되므로 가중치 값이 사라집니다. 이 상태에서 a = arr[x][2]를 하려고 할 때 런타임 에러가 납니다.
+ 크루스칼 알고리즘을 사용하신 것 같은데, disjoint set이 최적화되지 않아서 10초가 걸리고 있습니다. Union by rank와 경로 압축을 사용하여 0.5초 정도로 줄일 수 있습니다.
http://bowbowbow.tistory.com/2...
이해하기가 조금 어려웠긴하지만 확실히 시간이 줄어드네요... 여러부분 가르쳐주셔서 감사합니다 ㅎㅎ
댓글을 작성하려면 로그인해야 합니다.
ponta12 6년 전