이 문제는 그리디 알고리즘의 일종인 크루스칼 알고리즘으로 풀었다.
크루스칼 알고리즘은 전에도 적었지만 가중치가 최소인 최소 스패닝 트리를 구할 때 사용하는 알고리즘이다.
해결 방법은
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
struct edge {
int node[2];
int value;
edge(int a, int b, int c){
this->node[0] = a;
this->node[1] = b;
value = c;
}
bool operator<(edge &a){
return this->value < a.value;
}
};
vector<edge> e;
int parent[101];
int find_parent(int n){
if(parent[n] == n) return n;
else return find_parent(parent[n]);
}
void union_parent(int a, int b){
a = find_parent(a);
b = find_parent(b);
if(a < b)
parent[b] = a;
else
parent[a] = b;
}
bool find(int a, int b){
a = find_parent(a);
b = find_parent(b);
if(a == b) return false;
else return true;
}
int solution(int n, vector<vector<int>> costs) {
int answer = 0;
for(int i = 0; i < costs.size(); i++)
e.push_back(edge(costs[i][0],costs[i][1],costs[i][2]));
sort(e.begin(), e.end());
for(int i = 0; i < n; i++){
parent[i] = i;
}
for(int i = 0; i < e.size(); i++){
if(find(e[i].node[0], e[i].node[1])){
answer += e[i].value;
union_parent(e[i].node[0], e[i].node[1]);
}
}
return answer;
}