[프로그래머스][Python] 섬 연결하기

문제를 정리해보자.

 

n개의 섬 사이에 다리를 건설하는 비용이 주어진다.

최소의 비용으로 모든 섬이 통행 가능하도록 만든다.

따라서 최소 비용이 얼마인지 구해야 한다.

 

 

풀이를 생각해보자.

 

모든 섬을 방문한다. 그런데 최소 비용으로 방문한다.

최소 신장 트리이다. 

 

 

구현해보자.

 

프림 알고리즘을 이용하자.

 

 

import heapq


def solution(n, costs):
    graph = [[] for _ in range(n)]

    for li in costs:
        graph[li[0]].append([li[2], (li[0], li[1])])
        graph[li[1]].append([li[2], (li[1], li[0])])

    count = 0  # 방문 노드 개수
    dp = [0] * n  # 방문 노드
    result = 0  # 가중치 합

    order = []  # 방문 순서

    for edge in graph[0]:
        heapq.heappush(order, edge)  # 최소 힙

    while count < n-1:  # n개의 노드 방문

        node = heapq.heappop(order)

        A = node[1][0]
        B = node[1][1]
        val = node[0]

        if dp[A] == 0 or dp[B] == 0:
            dp[A] = 1
            dp[B] = 1

            result += val

            now_node = B
            count += 1

            for edge in graph[now_node]:
                heapq.heappush(order, edge)

    return result


print(solution(4, [[0, 1, 1], [0, 2, 2], [1, 2, 5], [1, 3, 1], [2, 3, 8]]))

 

 

처음에는 '다익스트라 알고리즘을 사용할까?'라고 생각했다.

하지만 안된다. 왜 다익스트라 알고리즘을 사용하면 안될까?

다익스트라 알고리즘과 프림 알고리즘의 차이점을 생각해보자.

 

 

다익스트라 알고리즘

 

 

 

 

다익스트라 알고리즘은 무향, 유향 그래프 모두 동작하며 최단 경로 트리를 만든다.

하나의 정점에서 다른 모든 정점의 최단 경로를 구한다.

즉, 정점과 정점 사이의 최단 경로를 구한다. ( 예) 1->3 : 2 )

 

 

프림 알고리즘

 

 

 

 

 

프림 알고리즘은 무향 그래프에서만 동작하며 최소 신장 트리를 만든다.

모든 정점을 최단 경로로 연결시킨다.

따라서 다익스트라와 달리 정점과 정점 사이가 최단 거리가 아닐 수도 있다. ( 예) 1->3 : 3 )

(즉, 최소 신장 트리가 최단 경로 트리를 보장하지 않고, 반대도 마찬가지로 보장하지 않는다.)

 

 

---

 

 

 

다시 말하자면, 다익스트라 알고리즘은 총 비용을 고려하지 않는다. 

따라서 프림 알고리즘을 사용해야 한다.

 

 

이미지 출처