매일 C++ day 9 / 섬 연결하기

2021-05-31

섬 연결하기

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

최소신장트리

출발지점을 from, 도착지점을 to라 할 때

find_parent(to)는 find_parnet(from)을 반환한다.

섬 {0, 1, 2, …. , n} 이 있을 때

모든 섬의 find_parent()의 반환값이 섬 0이 되도록 한다.

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

using namespace std;

bool cmp(vector<int> a, vector<int> b)
{
	return a[2] < b[2];
}

int find_parent(int parent[], int n) 
{
	if (parent[n] == n) return n;
	return find_parent(parent, parent[n]);
}

int solution(int n, vector<vector<int>> costs) 
{
    int answer = 0;
    int parent[n];
    for(int i=0; i<n; i++)
	 	parent[i] = i;
	sort(costs.begin(),costs.end(), cmp);	

	for(auto it:costs)
	{
		int a=find_parent(parent, it[0]), b=find_parent(parent, it[1]);
		if(a!=b)
		{
			a<b ? parent[b]=a : parent[a]=b;	
			answer += it[2];
		}
	}
    return answer;
}