つなぎ島
2548 ワード
https://programmers.co.kr/learn/courses/30/lessons/42861
クルーズアルゴリズム:ノードを最小限のコストで接続ノード数で初期化する.
関数getparentを作成して 親ノード を取得
コスト順ノード サイクルがない場合は、->getparent関数を使用します.
firstsecod=firstを決定し、parent[Secod]=firstに更新します. 費用を追加します.
クルーズアルゴリズム:ノードを最小限のコストで接続
#include <algorithm>
#include <string>
#include <vector>
using namespace std;
int parent[101] = { 0, };
int getparent(int node)
{
if (parent[node] == node) return node;
return getparent(parent[node]);
}
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(), [](vector<int> a, vector<int> b) {
if (a[2] == b[2])
{
if (a[0] == b[0])
{
return a[1] < b[1];
}
return a[0] < b[0];
}
else
{
return a[2] < b[2];
}
});
for (int i = 0; i < costs.size(); i++)
{
int First = getparent(costs[i][0]);
int Second = getparent(costs[i][1]);
int cost = costs[i][2];
if (First != Second)
{
parent[Second] = First;
answer += cost;
}
}
return answer;
}
int main()
{
vector<vector<int>> vvTemp = { {0, 1, 1},{0, 2, 2},{1, 2, 5},{1, 3, 1},{2, 3, 8} };
int n = 4;
int rst = solution(n, vvTemp);
return 0;
}
親ノードを関数getparentを作成して
コスト順
firstsecod=firstを決定し、parent[Secod]=firstに更新します.
Reference
この問題について(つなぎ島), 我々は、より多くの情報をここで見つけました https://velog.io/@imalive77/섬-연결하기テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol