[10/18] 섬 연결하기

레벨3 문제
그리디

내 코드

import heapq
def solution(n, costs):
    arr = [[0] * n for _ in range(n)]
    edge_list = []
    cost = 0
    
    for i in costs:
        arr[i[0]][i[1]] = i[2]
        arr[i[1]][i[0]] = i[2]
        
    check = [False] * n
    check[0] = True
    
    # 0번 노드에 연결된 엣지들 넣어주기
    for i in range(n):
        if (arr[0][i] != 0):
            heapq.heappush( edge_list, [arr[0][i], 0, i] )
    
    while ( False in check ):
        long, h, w = heapq.heappop(edge_list)
        print(h, w, long)
        
        # 이미 방문한 노드라면 지나가기
        if ( check[h] == True and check[w] == True ):
            continue
        
        # 둘중에 어떤 노드로 방문할지 결정 (w 처음 방문)
        if ( check[h] == True and check[w] == False ):
            check[w] = True
            cost += long
            
            for i in range(n):
                if (arr[w][i] != 0):
                    heapq.heappush(edge_list, [arr[w][i], w, i])
            
        # h 처음 방문
        else:
            check[h] = True
            cost += long
            
            for i in range(n):
                if (arr[h][i] != 0):
                    heapq.heappush(edge_list, [arr[h][i], h, i])
    
    return cost

로직

• 노드 방문했는지 확인하는 리스트
• 덩어리와 연결되어있는 엣지 정보가 들어있는 리스트 (힙)

1번 노드에서 시작해서, 가장 짧은 edge로 이동함

• 새로 방문한 노드는 체크해줌
• 덩어리와 새롭게 연결된 엣지는 추가해줌

피드백

• queue에 리스트를 넣었는데, 우선순위 queue는 [0]값 기준으로 작동한다.