프로그래머스 [Lv. 3] 섬 연결하기 {언어 : Python} [프림 알고리즘, 다시 풀어 보기]

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/42861?language=python3

프로그래머스

정답 코드

import heapq

def solution(n, costs):
    adjL = [[] for _ in range(n)]
    for start, to, cost in costs:
        adjL[start].append((cost, to))
        adjL[to].append((cost, start))
    
    visited = [False] * n
    min_heap = [(0, 0)]  # (cost, node)
    total_cost = 0
    edges_used = 0

    while min_heap and edges_used < n:
        cost, node = heapq.heappop(min_heap)
        if visited[node]:
            continue
        
        visited[node] = True
        total_cost += cost
        edges_used += 1
        
        for next_cost, next_node in adjL[node]:
            if not visited[next_node]:
                heapq.heappush(min_heap, (next_cost, next_node))

    return total_cost

풀이 방법

 

1. 인접 리스트 생성: 주어진 간선 정보를 기반으로 인접 리스트(adjL)를 생성한다.
2. 우선순위 큐(최소 힙) 초기화: 시작 노드(0)와 비용(0)을 최소 힙에 추가한다.
3. 프림 알고리즘 수행:
   1. 최소 힙에서 비용이 가장 작은 노드를 꺼낸다.
   2. 해당 노드를 방문하지 않았다면 방문 처리하고, 총 비용에 해당 간선 비용을 더한다.
   3. 방문한 노드와 연결된 모든 간선 중 방문하지 않은 노드로의 간선을 최소 힙에 추가한다.
4. 최소 신장 트리의 총 비용 반환: 모든 노드를 방문할 때까지 과정을 반복하며 최종적으로 최소 신장 트리의 총 비용을 반환하면 끝!

 

느낀점

• 최소 신장 트리(MST)에는 프림, 크루스칼이 있다.
• 다시 풀어보는게 좋을 것 같다.