[프로그래머스 42861 파이썬] 섬 연결하기 (level 3, MST)

알고리즘 유형 : MST
풀이 참고 없이 스스로 풀었나요? : O

https://school.programmers.co.kr/learn/courses/30/lessons/42861

소스 코드(파이썬)

import sys
INF = sys.maxsize

def solution(n, costs):
    answer = 0
    graph = [[] for _ in range(n)]
    dist = [INF]*n
    dist[0] = 0
    visited = [False]*n
    
    for edge in costs:
        a, b, c = edge
        graph[a].append((b, c))
        graph[b].append((a, c))
        
    for _ in range(n):
        fin_idx = None
        tmp = INF
        for i in range(n):
            if dist[i] < tmp and visited[i] == False:
                tmp = dist[i]
                fin_idx = i
        
        visited[fin_idx] = True
        answer += dist[fin_idx]
        
        for adj_node, w in graph[fin_idx]:
            if visited[adj_node] == False:
                dist[adj_node] = min(dist[adj_node], w)
        
    answer = sum(dist)
    return answer

풀이 요약

1. 모든 노드를 연결하되, 그 간선의 합이 최소가 되야하는 점에서 전형적인 MST 문제임을 알 수 있다. 크루스칼 또는 프림 어느 것으로도 풀 수 있다.

2. 프림 풀이가 익숙하지 않아서 프림으로 풀었다. 크루스칼과 달리 노드를 하나씩 확정하면서 MST를 구해나간다.

   dist[idx]는 MST 집합에서 idx로 도달하는 최소 비용을 의미한다.

   처음에 어떤 노드든 하나 골라 dist를 0으로 초기화한다.

   이 후 반복문을 n번 반복하는데 그 내용은 다음과 같다.

   dist 중 최소를 찾는다. 그 것은 곧 MST 집합에서 MST 집합에 속하지 않는 노드로 도달하는 가장 최소의 경우를 의미한다.

   이제 찾은 도착 노드의 인접 노드들의 dist 값을 연결된 간선의 가중치 값과, 원래의 dist[도착 노드] 값을 비교하여 최소로 갱신해주자.

   반복문을 모두 수행한 후 dist의 합을 다 더 해주면 MST에 사용된 간선들의 가중치 합을 구할 수 있다.

배운 점, 어려웠던 점

• 전형적인 MST 문제라 쉽긴 했는데, 최소 힙을 안쓰는 프림 알고리즘으로 풀어볼려다가 익숙지않아서 좀 헤맸다. 프림을 좀 많이 연습해야겠다.