[DAY-68] 프로그래머스 섬 연결하기

1. 문제

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

 

2. 문제 풀이

첫번째 문제 풀이 - bfs 사용(실패)

from collections import deque
def bfs(graph, visited, start):
    queue = deque([(start, 0)])
    visited[start] = True
    total_cost = 0
    
    while queue:
        
        node, sum_cost = queue.popleft()
        total_cost += sum_cost
        
        for neighbor, cost in graph[node]:
            if not visited[neighbor]:
                visited[neighbor]=True
                queue.append((neighbor, cost))
    
    return total_cost
                
                
def solution(n, costs):
    answer = 0
    visited = [False] * n
    graph = {i: [] for i in range(n)}
    
    for node1, node2, cost in costs:
        graph[node1].append((node2, cost))
        graph[node2].append((node1, cost))
        
   
    
    answer = bfs(graph, visited, 0)  
    return answer

 

문제를 풀면서 나도 어떻게 항상 최소 비용 선택을 보장하지?라고 생각했고

실제로 최소 비용 선택 보장을 못했다 ㅋ

지선생님한테 물어보니까 bfs 사용하려면 우선순위 큐를 사용하라고 하셨다

아무래도 최소 힙을 사용하면 항상 최소 비용 선택을 보장할 수 있으니까는..

 

 

두번째 문제 풀이 - bfs + 최소힙 사용 (성공) 

queue를 최소힙으로 정의하여 큐에 있는 노드 중 가장 최소 비용을 가진 노드를 탐색한다

만약 방문한적 있는 노드라면 다음 노드를 탐색하고, 아니라면 해당 노드의 방문 여부를 방문으로 변경하고, 총 비용에 현재 노드의 비용을 추가한다

현재 노드와 연결된 다른 노드들을 queue에 넣어 다시 최소 비용을 가진 노드를 탐색할 수 있게한다

import heapq
def bfs(graph, visited, start):
    queue = [(0, start)]
    total_cost = 0
    
    while queue:
        
        sum_cost, node = heapq.heappop(queue)
        
        if visited[node]:
            continue
        
        visited[node] = True
        total_cost += sum_cost
        
        for neighbor, cost in graph[node]:
            if not visited[neighbor]:
                heapq.heappush(queue, (cost, neighbor))
    
    return total_cost
                
                
def solution(n, costs):
    answer = 0
    visited = [False] * n
    graph = {i: [] for i in range(n)}
    
    for node1, node2, cost in costs:
        graph[node1].append((node2, cost))
        graph[node2].append((node1, cost))
    
    answer = bfs(graph, visited, 0)  
    return answer

 

 

 

여러 엣지 중에서 최소 비용을 가진 것만 찾아서 연결하면 아무래도 최소 비용으로 연결하는 것이 가능해지니까... 

최소힙 사용은 생각도 못했는데 좋다..