title: "[프로그래머스] 섬 연결하기 Python 파이썬 해설 (Level 3) - 이도훈"
cleanUrl: "programmers/42861"
description: "프로그래머스 Level 3 문제 [섬 연결하기]의 풀이를 정리합니다."

문제 설명 및 제한사항

아이디어 및 해결 방법

코드

from queue import PriorityQueue
from collections import defaultdict

def solution(n, costs):
    A = defaultdict(list)
    for u, v, w in costs:
        A[u].append((v, w))
        A[v].append((u, w))
        
    # MST 문제. 프림으로 구현해보자
    q = PriorityQueue()
    s = {0}
    # 트리에 0을 추가하면서 시작.
    for v, w in A[0]:
        q.put((w, v))
    
    answer = 0
    while len(s) < n:
        w, u = q.get()
        
        if u in s:
            continue

        s.add(u)
        answer += w
        
        for v, w in A[u]:
            if v in s:
                continue
            q.put((w, v))
            
    return answer

출처

프로그래머스 코딩테스트 연습 https://school.programmers.co.kr/learn/challenges