[알고리즘C++] 섬 연결하기

오늘의 문제

https://programmers.co.kr/learn/courses/30/lessons/42861

섬 연결하기

나의 풀이

#include <string>
#include <vector>

using namespace std;

int solution(int n, vector<vector<int>> costs) {
    int answer = 0;
    // 모든 섬을 건널 수 있는 최소 값 길 찾으라
    // 다익스트라
    vector<int> dij(n, 987654321);
    vector<vector<pair<int, int>>> node(n);
    for(int i=0;i<costs.size();i++){
        node[costs[i][0]].push_back(make_pair(costs[i][1], costs[i][2]));
        node[costs[i][1]].push_back(make_pair(costs[i][0], costs[i][2]));
    }
    dij[0] = -1;
    for(int i=0;i<node[0].size();i++){
        dij[node[0][i].first] = node[0][i].second;
    }
    for(int i=0;i<n-1;i++){
        int minN;
        int mini = 987654320;
        for(int j=0;j<n;j++){
            if(dij[j] == -1)
                continue;
            if(mini > dij[j]){
                minN = j;
                mini = dij[j];
            }
        }
        answer += dij[minN];
        for(int j=0;j<node[minN].size();j++){
            dij[node[minN][j].first] = min(dij[node[minN][j].first], node[minN][j].second); 
        }
        dij[minN] = -1;
    }
    return answer;
}

모범 답안

#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int d[101];

int getParent(int node){
    if(node == d[node]){
        return node;
    }
    else return d[node] = getParent(d[node]);
}

bool compare(vector<int> a, vector<int> b){
    return a[2] < b[2];
}

int solution(int n, vector<vector<int>> costs) {

    int answer = 0;
    for(int i =0; i<n; i++){
        d[i] = i;
    }
    sort(costs.begin(), costs.end(), compare);
    for(int i=0; i<costs.size(); i++){
        int start = getParent(costs[i][0]);
        int end = getParent(costs[i][1]);
        int cost = costs[i][2];

        if(start != end){
            d[end] = start;

            answer += cost;
        }
    }


    return answer;
}

배울 점

• 최단경로와 관련되어있길래 다익스트라로 문제를 풀어봤다
• 플로이드와샬로 풀어보려 했는데 적절하진 않은것 같다.

• 사실 작은것만 선택하면 풀리는 문제다. 저 사람은 정렬로 문제를 풀었네