섬 연결하기

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;

}

1. 노드 개수만큼 부모노드 초기화
2. 부모노드 구하는 함수 getparent 작성
3. 노드를 비용순으로 정렬
4. 사이클이 없다면 -> getparent함수 이용
   first second 정하고 나서 parent[secod] = first 로 업데이트 하고
5. 비용추가한다.