[프로그래머스] 섬 연결하기

분류 : MST, 최소스패닝 트리

 

요구사항

모든 섬을 연결하는 최소 비용 구하기

 

풀이

크루스칼 알고리즘

1. 간선의 가중치를 오름차순으로 정렬하기

2. 간선이 작은 순 부터 연결하기

3. 연결간선 숫자가 n-1일때 종료

 

풀이 방법은 프림, 크루스칼 있으나 크루스칼으로 풀이하였다

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
struct go {
	int x;
	int y;
	int z;
};
int n, m;
vector<go> v;
int dist[1100];
int parent[1100];
int Find(int x) {
	if (parent[x] == x) return x;
	else return x = Find(parent[x]);
}
void Union(int x, int y) {
	x = Find(x);
	y = Find(y);
	if (x != y) {
		parent[x] = y;
	}
}
bool com(go a, go b) {
	if (a.z < b.z) return true;
	return false;
}

int solution(int n, vector<vector<int>> costs) {
	int answer = 0;
	int costsize = costs.size();
	for (int i = 0; i < costsize; i++) {
		int x = costs[i][0];
		int y = costs[i][1];
		int z = costs[i][2];
		v.push_back({ x,y,z });
	}
	for (int i = 1; i <= n; i++) parent[i] = i;
	sort(v.begin(), v.end(), com);
	int vsize = v.size();
	int cnt = 0;
	for (int i = 0; i < vsize; i++) {
		cout << i << endl;
		int x = Find(v[i].x);
		int y = Find(v[i].y);
		int z = v[i].z;
		if (x != y) {
			cout << "Z" << z << endl;
			Union(x, y);
			answer += z;
			cnt++;
		}
		if (cnt == n - 1) break;
	}
	
	return answer;
}