[C++] 백준 10423번: 전기가 부족해

문제 링크

10423번: 전기가 부족해

문제 요약

한 나라에 여러 개의 발전소가 있는 도시가 있다. 이 나라에서 한 쌍의 도시 사이에는 케이블을 설치할 수 있다. 케이블을 설치할 수 있는 도시 쌍들과 설치 비용이 주어질 때, 모든 도시가 발전소에 연결될 수 있도록 하는 최소 설치 비용을 구해야 한다.

접근 방법

최소 비용으로 모든 정점을 연결해야 하기 때문에, 최소 스패닝 트리를 떠올려 볼 수 있습니다.

단, 이 문제의 경우 발전소가 여러개 존재한다는 것이 최소 스패닝 트리의 기본 문제와는 다른 점입니다. 이를 해결하는 방법은 간단한데, 발전소가 있는 정점들을 최소 스패닝 트리를 만들기 전에 미리 하나로 합치는 것입니다.

간단하게 발상을 할 수 있는 부분인지라 700명 넘게 푼 골드2 문제지만 정답률이 70퍼센트가 넘어갑니다.

제 경우에는 크루스칼 알고리즘을 이용해서 구현했습니다.

코드

#include <bits/stdc++.h>
#define VPRT(x, type) copy(x.begin(), x.end(), ostream_iterator<type>(cout, " "))
#define ALL(x) x.begin(), x.end()
#define FASTIO ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define endl '\n'
#define MAX 1001

using namespace std;

struct Info {
	int u, v, w;
};

int parent[MAX];
vector<Info> info;

bool compare(const Info& a, const Info& b) { return a.w < b.w; }

int Find(int a)
{
	if (a == parent[a])
		return a;
	return parent[a] = Find(parent[a]);
}

void Union(int a, int b)
{
	int pa = Find(a), pb = Find(b);
	parent[pa] = pb;
}

int main(void)
{
	FASTIO;

	int n, m, k;
	cin >> n >> m >> k;

	for (int i = 1; i <= n; i++)
		parent[i] = i;

	vector<int> tmp;
	for (int i = 0; i < k; i++)
	{
		int city;
		cin >> city;
		tmp.push_back(city);
	}

	for (int i = 1; i < tmp.size(); i++)
		Union(tmp[0], tmp[i]);

	for (int i = 0; i < m; i++)
	{
		int u, v, w;
		cin >> u >> v >> w;
		info.push_back({ u, v, w });
	}

	sort(ALL(info), compare);

	int res = 0;
	for (auto& i : info)
		if (Find(i.u) != Find(i.v))
			res += i.w, Union(i.u, i.v);

	cout << res << endl;
	return 0;
}