섬 연결하기
학습 키워드 : 그리디(Greedy), 프림(prim), 우선순위 큐, 최소 신장 트리(MST)
문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/42861
문제 설명
n개의 섬 사이에 다리를 건설하는 비용(costs)이 주어질 때, 최소의 비용으로 모든 섬이 서로 통행 가능하도록 만들 때 필요한 최소 비용을 return 하도록 solution을 완성하세요.
다리를 여러 번 건너더라도, 도달할 수만 있으면 통행 가능하다고 봅니다. 예를 들어 A 섬과 B 섬 사이에 다리가 있고, B 섬과 C 섬 사이에 다리가 있으면 A 섬과 C 섬은 서로 통행 가능합니다.
제한 사항
- 섬의 개수 n은 1 이상 100 이하입니다.
- 임의의 i에 대해, costs[i][0] 와 costs[i][1]에는 다리가 연결되는 두 섬의 번호가 들어있고, costs[i][2]에는 이 두 섬을 연결하는 다리를 건설할 때 드는 비용입니다.
- 같은 연결은 두 번 주어지지 않습니다. 또한 순서가 바뀌더라도 같은 연결로 봅니다. 즉 0과 1 사이를 연결하는 비용이 주어졌을 때, 1과 0의 비용이 주어지지 않습니다.
- 모든 섬 사이의 다리 건설 비용이 주어지지 않습니다. 이 경우, 두 섬 사이의 건설이 불가능한 것으로 봅니다.
- 연결할 수 없는 섬은 주어지지 않습니다.
문제 풀이
import heapq
def solution(n: int, costs: list):
graph = [[] for _ in range(n+1)]
connected = [False for _ in range(n+1)]
for cost in costs:
a,b,c = cost
graph[a].append([c,b])
graph[b].append([c,a])
def prim(st):
q = []
total_cost = 0
heapq.heappush(q,(0,st))
while q:
cost, node = heapq.heappop(q)
if not connected[node]:
connected[node] = True
total_cost+=cost
for i in graph[node]:
if not connected[i[1]]:
heapq.heappush(q,i)
return total_cost
return prim(0)
무방향, 가중치가 있는 간선의 최솟값이기 때문에 최소 신장 트리를 푸는 알고리즘을 채택했다. 프림 알고리즘은 우선순위 큐를 사용해서 아직 트리에 연결되지 않으면서 트리안에 있는 노드에 연결된 간선 중 가장 작은 가중치를 가지는 간선을 우선적으로 꺼낸다. 큐 안에 있는 cost중 그 때 그 때 가장 작은 값을 무조건 꺼낸 다는 점에서 상황마다 가장 크거나 작은 값을 우선적으로 선택하는 그리디 알고리즘과도 일맥상통한다.
코멘트
최소 신장 트리를 푸는 알고리즘에는 그 외에도 크루스칼 알고리즘이 있다. 크루스칼 알고리즘은 프림 알고리즘과는 다르게 출발 노드를 받지 않고 그래프에서 가중치가 가장 작은 간선부터 이으면서 사이클이 생기는 순간 그 간선은 무시하고 다음 간선을 잇는 알고리즘이다.
문풀 백업