[프로그래머스] Lv.3 섬 연결하기 [Python, 파이썬]

• 문제 : https://school.programmers.co.kr/learn/courses/30/lessons/42861
• 🔑 프림 알고리즘
  • 출발 위치는 상관없음
  • 현재 섬에서 갈 수 있는 섬들을 큐에 넣고 비용이 가장 적은 길을 뽑아내 섬을 연결하는 방식
  • 큐를 힙으로 구현했기 때문에 항상 최소 비용의 길을 뽑아내서 이동함
  • 최소 비용의 길을 뽑아서 갔으면 또 갈 필요가 없기 때문에 방문 리스트를 통해 못 가게 막음

 

from collections import defaultdict
from heapq import heappush, heappop

def solution(n, costs):
    answer = 0
    graph = defaultdict(list)
    
    for cost in costs:
        graph[cost[0]].append((cost[2], cost[1]))   # 섬1 : [(비용, 섬2)]
        graph[cost[1]].append((cost[2], cost[0]))
    
    visit = [False] * n
    q = [(0, 0)]
    
    while q:
        cost, node = heappop(q)
        
        if not visit[node]:
            visit[node] = True
            answer += cost
            
            for next_cost, next_node in graph[node]:
                heappush(q, (next_cost, next_node))
    
    return answer