[프로그래머스] Level 3 섬 연결하기 python

https://programmers.co.kr/learn/courses/30/lessons/42861#

코딩테스트 연습 - 섬 연결하기

프림 알고리즘으로 풀었다. 크루스칼로도 풀어도 될듯

from heapq import heappop, heappush
def solution(n, costs):
    answer = 0
    adj_list = [[] for _ in range(n)]
    for s, e, c in costs:
        adj_list[s].append((c, e))
        adj_list[e].append((c, s))
    # prim
    visit = [0 for _ in range(n)]
    h = [(0, 0)]
    while h:
        cur_d, cur = heappop(h)
        if visit[cur]:
            continue
        visit[cur] = 1
        answer += cur_d
        for adj_d, adj in adj_list[cur]:
            heappush(h, (adj_d, adj))
        
    return answer