백준 1197 - 최소 스패닝 트리

문제링크

• 백준 1197

문제설명

• 정점의 개수(V)와 간선의 개수(E)가 주어진다.
• E개의 줄에 걸쳐 간선의 정보(A, B, C)가 주어진다.
  • 두 정점 A와 B는 가중치 C 간선으로 연결되어 있다.
• 최소 비용 트리의 가중치를 구하라

문제접근

• 크루스칼 알고리즘
  • 비용이 적은 순서대로 간선 정보를 정렬한다.
  • 두 정점이 서로 다른 그룹에 속해 있다면 연결한다.
  • 연결하고 나면 그룹의 번호가 작은 그룹으로 합친다.
• 간선 정보를 담는 배열은 vector<vector<int>> costs 형태로 담는게 편하다.
  • costs[idx][2] 는 costs[idx][0] -> costs[idx][1] 로 가기 위해 필요한 비용

구현

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <memory.h>
using namespace std;

int v, e;
int group[10001];
// costs[i][0] : from, costs[i][1] : to, costs[i][2] : w
vector<vector<int>> costs;

// 비용이 적은 순서대로 정렬
bool cmp(vector<int> v1, vector<int> v2) {
	return v1[2] < v2[2];
}

int findGroup(int node) {
	if (node == group[node]) return node;
	return findGroup(group[node]);
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	scanf("%d %d", &v, &e);
	int ans = 0;

	for (int i = 0; i < e; i++) {
		int from, to, w;
		scanf("%d %d %d", &from, &to, &w);
		vector<int> node = { from, to, w };
		costs.push_back(node);
	}
	sort(costs.begin(), costs.end(), cmp);

	// init group
	for (int i = 0; i < v; i++) {
		group[i] = i;
	}

	for (int i = 0; i < costs.size(); i++) {
		int from = costs[i][0];
		int to = costs[i][1];
		int w = costs[i][2];

		int gfrom = findGroup(from);
		int gto = findGroup(to);
		if (gfrom != gto) {
			ans += w;
			if (gfrom < gto) group[gto] = gfrom;
			else group[gfrom] = gto;
		}
	}

	printf("%d\n", ans);
	return 0;
}