(파이썬) [알고리즘 문제 풀이] - 섬 연결하기 (프로그래머스

오늘은 프로그래머스에서 섬 연결하기를 풀어보았습니다.

설명

n개의 섬 사이에 다리를 건설하는 비용(costs)이 주어질 때, 최소의 비용으로 모든 섬이 서로 통행 가능하도록 만들 때 필요한 최소 비용을 return 하도록 solution을 완성하세요.

다리를 여러 번 건너더라도, 도달할 수만 있으면 통행 가능하다고 봅니다. 예를 들어 A 섬과 B 섬 사이에 다리가 있고, B 섬과 C 섬 사이에 다리가 있으면 A 섬과 C 섬은 서로 통행 가능합니다.

제한사항

• 섬의 개수 n은 1 이상 100 이하입니다.
• costs의 길이는 ((n-1) * n) / 2이하입니다.
• 임의의 i에 대해, costs[i][0] 와 costs[i] [1]에는 다리가 연결되는 두 섬의 번호가 들어있고, costs[i] [2]에는 이 두 섬을 연결하는 다리를 건설할 때 드는 비용입니다.
• 같은 연결은 두 번 주어지지 않습니다. 또한 순서가 바뀌더라도 같은 연결로 봅니다. 즉 0과 1 사이를 연결하는 비용이 주어졌을 때, 1과 0의 비용이 주어지지 않습니다.
• 모든 섬 사이의 다리 건설 비용이 주어지지 않습니다. 이 경우, 두 섬 사이의 건설이 불가능한 것으로 봅니다.
• 연결할 수 없는 섬은 주어지지 않습니다.

풀이

주어진 그래프에 대하여 최소한의 비용으로 모든 노드들을 연결하는 문제입니다.

이 문제를 푸는 알고리즘은 대표적으로 크루스칼과 프림이 있는데요.

저는 프림 알고리즘을 사용 하였습니다.

프림 알고리즘을 어떻게 작동하는지 설명하기 위해 예시를 하나 준비 했습니다.

글로 설명하는것 보다 눈으로 보는게 알고리즘 이해에는 빠른것 같아요.

시작할 노드를 한개 정합니다. (어느 노드에서 시작해도 괜찮습니다.)

그리고 빈 리스트를 한개 준비합니다. 이 리스트는 어떤 용도냐면

연결된 노드들을 담는 용도로 사용합니다. 그 이유는 이미 연결 노드를 또 다시 갈 필요가 없기 때문입니다.

visited = [] 라고 부르겠습니다.

저는 예시에서 노드 B를 택했습니다. 

visited = [B]

B에서 갈수 있는 간선 중에 가장 저렴한 간선을 택합니다.

B에서 갈수 있는 간선은 2개가 있는데 4가 10보다 가격이 저렴하기 때문에

D로 가는 간선을 택합니다. 

visited = [B,D]

이미 선택해서 연결한 간선은 실선으로 표기하고

다음 연결 가능한 간선들은 점선으로 표기 하도록 하겠습니다.

B와 D는 연결이 되었습니다.

이제는 B와 D에서 다른 노드로 갈수 있는 간선 중에 가장 저렴한 간선을 선택하면 됩니다.

D에서 E로 가는 간선이 가격 1로 가장 저렴하기 때문에 D와 E를 연결하도록 하겠습니다.

visited = [B,D,E]

C는 아직 연결되지 않았고 D에서 C로 가는 간선이 가격 2로 가장 저렴하기 때문에

D와 C도 연결 시킵니다.

그럼 visited = [B,D,E,C]가 됩니다.

이미 지나온 노드들을 빼고나니 A로 가는 간선 밖에 남지 않았습니다.

그래서 C에서 A로 가는 간선을 연결 시키겠습니다.

visited = [B,D,E,C,A] 가 되고 모든 노드들을 연결 시켰기 때문에 더 이상 탐색을 멈추고

총 비용을 계산 하도록 하겠습니다.

5개의 노드를 연결 시키는 최소 비용은 4+1+2+3 = 10

정리해보자면,

• 임의로 정한 노드 1개에서 시작 (1개의 노드만 있는 트리)
• 트리에서 연결 되어 있지 않은 노드로 갈수 있는 간선 중에 가장 저렴한 간선 선택해서 트리에 포함 시킴
• 모든 노드가 포함될때까지 계속
•  

코드

 

import heapq as hq
from collections import defaultdict

def solution(n, costs):
    answer = 0
    my_dict = defaultdict(list)
    visited = set()
    
    for temp in costs:
        my_dict[temp[0]].append([temp[2],temp[1]])
        my_dict[temp[1]].append([temp[2],temp[0]])
        
    que = []
    hq.heapify(que)
    
    for item in my_dict[0]:
        hq.heappush(que,item)
    visited.add(0)
    
    while que and len(visited) < n:
        bridge = hq.heappop(que)
        
        if bridge[1] not in visited:
            visited.add(bridge[1])
            answer += bridge[0]
            
            for item in my_dict[bridge[1]]:
                hq.heappush(que, item)
                
    return answer