문제 설명 및 제한사항
아이디어 및 해결 방법
코드
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
Python
복사
출처
프로그래머스 코딩테스트 연습 https://school.programmers.co.kr/learn/challenges