문제

문제설명
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의 비용이 주어지지 않습니다.
• 모든 섬 사이의 다리 건설 비용이 주어지지 않습니다. 이 경우, 두 섬 사이의 건설이 불가능한 것으로 봅니다.
• 연결할 수 없는 섬은 주어지지 않습니다.

---

해결과정

이 문제는 섬을 모두 방문할 수 있도록 최소의 비용으로 섬 사이의 다리를 건설하는 그리디 문제 입니다.

그리디(Greedy): 현재 상황에서 가장 좋아보이는 것만을 선택하는 알고리즘

1트(성공)

prim 알고리즘과 우선순위 큐를 사용했습니다.

우선순위 큐(Priority queue): 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나오는 형태의 자료구조

prim 알고리즘은 각 단계마다 현재 연결된 노드들 중 최소 비용의 간선을 선택하면서 MST를 구성해 나가는 반면, kruskal 알고리즘은 모든 간선을 비용에 따라 오름차순 정렬한 뒤, 사이클을 형성하지 않는 간선을 선택하면서 MST를 구성합니다.
이 때문에 간선의 개수가 많은 경우를 생각해 prim 알고리즘이 효율적이라고 판단했습니다.

1. 주어진 costs를 인접 리스트 형태로 변환합니다.
2. 우선 시작 정점을 방문한 것으로 처리합니다.
3. 시작 정점과 연결된 간선을 heap에 추가합니다.
4. heap에서 최소 가중치를 가지는 간선을 pop하고, 해당 간선의 끝점 노드가 이미 방문한 노드인 경우에는 다음 간선을 검사합니다. 그렇지 않은 경우, 끝점 노드를 방문한 것으로 처리하고 result에 해당 간선의 가중치를 더합니다.
5. 해당 끝점 노드와 연결된 간선을 heap에 추가합니다.
6. 4, 5의 과정을 heap이 빌 때까지 반복합니다.

Code

import heapq

def solution(n, costs):
    graph = [[] for _ in range(n)]
    for cost in costs:
        graph[cost[0]].append((cost[1], cost[2]))
        graph[cost[1]].append((cost[0], cost[2]))
    
    start = 0
    visited = [False] * len(graph)
    visited[start] = True
    heap = []
    result = 0
    
    for node, weight in graph[start]:
        heapq.heappush(heap, (weight, start, node))
    
    while heap:
        weight, start, node = heapq.heappop(heap)
        if visited[node]:
            continue
        
        visited[node] = True
        result += weight
        
        for next_node, next_weight in graph[node]:
            heapq.heappush(heap, (next_weight, node, next_node))
            
    return result

위 코드의 시간 복잡도는 O(ElogV) 입니다.