[프로그래머스][그리디][C++] 섬 연결하기

문제

프로그래머스 그리디 - 섬 연결하기 (Level 3)

코딩테스트 연습 - 섬 연결하기

 

---

문제 풀이

접근 방식

모든 섬을 연결하는 최소 비용을 구하는 문제이다.

이 문제는 프림 알고리즘을 활용하여 문제를 해결하였다.

 

우선, 주어진 costs 벡터를 활용하여 인접 행렬을 만들어주었다.

그 후, 방문한 섬과 방문하지 않은 섬의 인덱스를 구분해주기 위해,

시작 위치인 0을 visited 벡터에 넣고, 그 외의 섬들의 인덱스를 unvisited 벡터에 넣어주었다.

 

while문에서는 프림 알고리즘을 활용하여 다리를 선택해주었다.

즉, 방문한 섬에서 방문하지 않은 섬으로 연결할 수 있는 다리들 중 최소 비용이 드는 다리를 선택해주었다.

선택한 다리와 연결되어 있는 섬은 방문한 섬에 추가하고, 방문하지 않은 섬에서 제거해주었다.

 

위의 방식을 n - 1개의 다리를 선택할 때까지 수행하여 최종적인 최소 비용을 구해주었다.

(n - 1개의 다리를 설치해야 모든 섬을 연결할 수 있다.)

 

---

풀이 코드 - C++

#include <vector>
using namespace std;

int solution(int n, vector<vector<int>> costs) {
    int answer = 0;
    vector<vector<int>> graph(n,vector<int>(n));
    int len = costs.size();
    for(int i = 0; i < len; i++){
        graph[costs[i][0]][costs[i][1]] = costs[i][2];
        graph[costs[i][1]][costs[i][0]] = costs[i][2];
    }
    vector<int> visited;
    visited.push_back(0);
    vector<int> unvisited;
    for(int i = 1; i < n; i++) unvisited.push_back(i);
    int cnt = 1;
    while(cnt != n){
        int min = 10000000;
        int min_index = 0;
        for(int i = 0; i < cnt; i++){
            for(int j = 0; j < n - cnt; j++){
                if(graph[visited[i]][unvisited[j]] > 0 && min > graph[visited[i]][unvisited[j]]){
                    min = graph[visited[i]][unvisited[j]];
                    min_index = j;
                }
            }
        }
        cnt++;
        visited.push_back(unvisited[min_index]);
        unvisited.erase(unvisited.begin() + min_index);
        answer += min;
    }
    return answer;
}

실행 결과

실행 결과 : 100.0