코딩 테스트 - 섬 연결하기

섬 연결하기

문제 링크 : 섬 연결하기

문제 설명

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

입출력 예

n	costs	return
4	[[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]]	4

풀이 방법

• 모든 섬이 서로 통행 가능하도록 만드는 최소 비용을 구하는 문제이기 때문에, 0번째 섬을 기준으로 가장 작은 비용을 가지는 다리를 선택해나가면서, 새로운 섬을 연결할 때마다 새로운 섬과 기존의 비용을 비교해서 작은 값을 기준으로 업데이트해나가면서 모든 섬을 연결할 때까지 하도록 하는 알고리즘을 사용할 것이다.
  -> 해당 풀이법은 O(V^2)의 시간복잡도를 가지고, V는 최대 100이기 때문에 알맞은 알고리즘으로 보인다.

구현

#include <string>
#include <vector>
#include <climits>

using namespace std;

int solution(int n, vector<vector<int>> costs) {
    vector<vector<int>> graph(n, vector<int>(n, INT_MAX));
    
    // costs 값을 그래프로 변환하기
    for(vector<int> v : costs){
        graph[v[0]][v[1]] = v[2];
        graph[v[1]][v[0]] = v[2];
    }
    
    // 0번째 섬을 기준으로 최소값 구하기
    int answer = 0;
    vector<int> lowCost(n);
    vector<bool> visited(n, false);
    for(int i = 0; i < n; i++){
        lowCost[i] = graph[0][i];
    }
    visited[0] = true;
    int count = 0;
   
    while(count < n - 1){
        int minValue = INT_MAX;
        int minIndex = 0;
        for(int i = 1; i < n; i++){
            if(!visited[i] && lowCost[i] < minValue){
                minValue = lowCost[i];
                minIndex = i;
            }
        }
        
        visited[minIndex] = true;
        count++;
        answer += minValue;
        
        // 새로운 섬을 추가할 때마다 최소값 갱신하기
        for(int i = 1; i < n; i++){
            if(!visited[i] && lowCost[i] > graph[minIndex][i]){
                lowCost[i] = graph[minIndex][i];
            }
        }
    }
    
    return answer;
}