[프로그래머스] 섬 연결하기.py

import math
def solution(n, costs):
    # 정렬했을 때 weight 가중치 작을수록 리스트 전면에 오도록 costs를 변경한다.
    costs = [(w, f, t) for f, t, w in costs]
    costs.sort()
    
    result = 0
    # 이미 방문한 노드는 저장한다.
    visited = set()
    
    # 가장 가중치 작은 것부터 연결한다
    w, f, t = costs[0]
    
    # 자기 자신을 연결하는 게 아니면, 첫 번째 노드 weight를 result에 저장한다.
    if f != t:
        result += w
    # 두 노드가 연결되었으므로 두 노드를 visited에 저장한다.
    visited.update([f,t])
    
    # 모든 노드가 연결될 때까지 반복한다.
    while len(visited) != n:
        # 연결할 수 있는 노드 weight의 최솟값을 찾아야 한다.
        _min = math.inf
        
        for w, f, t in costs:
            # from과 to 두 개의 노드 중 하나는 visited에 있어야 한다.
            # 즉 이미 연결된 노드들 중 하나여야 한다.
            if t in visited or f in visited:
                
                # 이미 둘 다 visited에 있으면,
                # 새로 들어온 weight는 기존에 연결된 두 노드의 weight보다 작을 수 없다.
                # from과 to가 같은 노드면 저장할 이유가 없음.
                if (f in visited and t in visited) or f == t:
                    continue
                
                # weight가 가장 작은 노드로 _min값을 업데이트한다.
                if _min > w:
                    _min = w
                    frm, to = f, t
        
        # 최소 weight를 result값에 더한다.            
        result += _min
        # 새로 연결한 두 개의 노드를 visited에 업데이트한다.
        visited.add(frm)
        visited.add(to)
        
    # while문을 빠져나오면, 모든 노드는 연결된 상태고
    # 각 노드를 연결하는 weight는 작은 순서대로 전부 찾은 상태.
    return result