섬 연결하기 C++

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

코딩테스트 연습 - 섬 연결하기

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

using namespace std;
int parent[101];
vector<pair<pair<int, int>, int>> v;
int N;

bool cmp(pair<pair<int, int>, int> a, pair<pair<int, int>, int> b) {
	if (a.second < b.second) return true;
	else return false;
}

int FindParent(int ii) {
	if (parent[ii] == ii) return ii;
	else return FindParent(parent[ii]);
}

void UnionParent(int ii, int jj) {
	int pi = FindParent(ii);
	int pj = FindParent(jj);
	if (pi > pj) {
		parent[pj] = pi;
	}
	else
		parent[pi] = pj;
}

int solution(int n, vector<vector<int>> costs) {
	int answer = 0;
	N = n;

	for (int i = 0; i < n; i++) {
		parent[i] = i;
	}

	for (int i = 0; i < costs.size(); i++) {
		v.push_back({ { costs[i][0],costs[i][1] }, costs[i][2] });
	}

	sort(v.begin(), v.end(),cmp);

	for (int i = 0; i < v.size(); i++) {
		int start = v[i].first.first;
		int end = v[i].first.second;
		int c = v[i].second;

		if (FindParent(start) == FindParent(end)) continue;

		answer += c;
		UnionParent(start, end);
	}

	return answer;
}