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