[백준] 6497 전력난.py

pseeej·2021년 8월 12일

Algorithms MST baekjoon kruskal

문제 링크 : https://acmicpc.net/problem/6497

💡 아이디어

문제를 어떤 방식으로 해결하려 했는지 그 과정을 적어주세요. 초기에 접근한 방법과 최종 접근이 차이가 없으면 한개만 적어도 됩니다.

초기 접근

이거 직전까지 썼던? 지난 주 강의까지 했던? 그냥 기본적인 크루스칼을 쓸까,,, 하다가 그러면 강의 들은 보람이 없을 것 같아서 이번 주차 강의를 또 이용했다.

최종 접근

이번 주 강의 두 개 역시 크루스칼에 관련된 강의였다. 다른 점이 있었다면, 지난 번은 그냥 각자의 집합을 기준으로 같은 집합 안에 있으면 이게 회전?이 일어나는 거고 그랬는데! 이번 거는 각 node들의 최종 head를 비교하는 방식이었다.

각 node의 최종 head를 다 본인으로 초기화
이어줄 vertex끼리의 최종 head 검사
1. 최종 head가 서로 같다 == 같은 graph 안에 있다 이므로 다음으로 넘어감
2. 최종 head가 서로 다를 경우
  1. 두 vertex가 속해 있는 graph의 깊이 구함
  2. 그 깊이를 기준으로 더 깊은? graph로 작은 게 들어가게 됨 (하나로 합침)
  3. 어떻게 들어가냐면! 더 깊은 graph에서의 head node의 자식으로 들어감
  4. 이런 과정 거치면 두 vertex의 최종 head 같아지게 됨

~~뭐 이런 과정...~~

📋 사용 스펙

어떤 알고리즘 또는 기법을 사용해 문제를 해결했는지 알려주세요

Kruskal
Minimum Spanning Tree

👨🏻‍💻 👩‍💻 코드

def getHead(node, cnt): # 헤드 구해주는 함수
    global head_list
    if head_list[node] != node:
        return getHead(head_list[node], cnt+1)
    else:
        # 여기에서의 cnt는 깊이를 말하는 거랄까,,,
        return (node, cnt)

while True:
    M, N = map(int, input().split())

    # ㅋㅋ 이 종료조건 이상해~
    if M==0 and N==0:
        break

    roads = []  # 아낀 돈 구해주기 위한,,,
    total_arr = []
    for i in range(N):
        a, b, c = map(int, input().split())
        roads.append(c)
        total_arr.append((a, b, c))

    # 거리 기준으로 정렬
    total_arr = sorted(total_arr, key = lambda dist:dist[2])
    # 각 node에 대한 head node 본인으로 초기화
    head_list = [i for i in range(M)]

    res = 0
    for elec in total_arr:
        verA, verB, dist = elec
        aHead, aCnt = getHead(verA, 0)
        bHead, bCnt = getHead(verB, 0)

        if aHead != bHead:
            res += dist
            # 깊이가 더 깊은 거에 짧은 거 넣어줄거야!
            if aCnt >= bCnt:
                head_list[bHead] = aHead
            else:
                head_list[aHead] = bHead

    print(sum(roads) - res)

부족했던 점

솔루션에 접근하기 까지 아쉬웠던 부분 들을 적어주세요. 솔루션을 참조하고나서야 고친 점들을 적어주세요. 솔루션의 링크도 적어주세요. 막힘 없이 구현했다면, 생략해도 좋습니다.

저거 입력하다가 무슨 'NoneType' object is not iterable 이라는 오류가 떴다. 웬만해선 오류 뜨는 거 그냥 내가 해석하고 해결하려고 하는데 뭔소린지 몰라서 검색해봤더니 함수에서 재귀 쓸 때,,, ~~C++에선 이런 거 안 났는데,,,~~ 함수에 return이 빠졌다고 난 오류였다. 그래서 부랴부랴 재귀 부분에도 return 써줬더니 됐따. 아래 링크 참고했음ㅋ

'NoneType' object is not iterable 오류 해결 방법