프로그래머스 레벨3 섬 연결하기

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

 

서론

전형적인 MST문제. 크루스칼 알고리즘을 이용하여 풀이

 

---

구현

// c++

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

int parent[101];

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

int find(int x){
    if(x == parent[x]) return x;
    else return parent[x] = find(parent[x]);
}

int merge(int a, int b){
    a = find(a);
    b = find(b);
    
    if(a == b) return false;
    else{
        if(a>b) parent[a] = b;
        else parent[b] = a;
    }
    return true;
}

int solution(int n, vector<vector<int>> costs) {
    int answer = 0;
    
    for(int i=0;i<n;i++){
        parent[i] = i;
    }
    
    sort(costs.begin(), costs.end(), compare);
    for(int i=0, size = costs.size();i<size;i++){
        if(merge(costs[i][0], costs[i][1]) == true){
            answer+=costs[i][2];
        }
    }
    
    for(int i=0;i<n;i++){
        cout<<parent[i]<<endl;
    }
    
    return answer;
}