つなぎ島


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

クルーズアルゴリズム:ノードを最小限のコストで接続
#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を作成して
  • 親ノード
  • を取得
    コスト順
  • ノード
  • サイクルがない場合は、->getparent関数を使用します.
    firstsecod=firstを決定し、parent[Secod]=firstに更新します.
  • 費用を追加します.