백준 10423번 전기가 부족해 / MST(크루스칼), 발전소 합치기

https://www.acmicpc.net/problem/10423

 

MST 크루스칼 문제고 잘 풀었다.

근데 티어 높은 다른 사람들 코드 보니까 좀 특이해서 아이디어 남겨둔다.

 

위의 이중원은 발전소고 단일원은 도시인데 하나의 도시 묶음에 발전소 2개가 들어가면 안된다.

그래서 난 Union할때 발전소 번호로 묶어줬고

Union하기 전에 둘 다 발전소 번호면 묶지 않게 조건 달아줬다.

그래서 잘 풀었다.

 

근데 다른 사람들 코드 보니 시작하자 마자 발전소 3개끼리 묶어버린다.

이러면 다른 도시들이 또 다른 발전소랑 그룹지으려 하면 사이클이 생기니 안묶는다.

되게 간단하고 신기한 아이디어다.

 

내 코드 남겨둔다. 

만약 발전소끼리 묶고 시작한다면 Union함수도 건들 필요 없고 if문도 깔끔했을 듯 하다.

#include <bits/stdc++.h>
using namespace std;

vector<int> parent;
vector<bool> power_plant;

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

void Union(int x, int y)
{
	x = Find(x);
	y = Find(y);
	if (power_plant[x]) parent[y] = x;
	else if (power_plant[y]) parent[x] = y;
	else {
		if (x < y) parent[y] = x;
		else if (x > y) parent[x] = y;
	}
}

int main()
{
	ios::sync_with_stdio(false); cin.tie(NULL);

	int N, M, K; // 도시갯수, 케이블수, 발전소수
	cin >> N >> M >> K;

	power_plant.resize(N + 1, false);
	int input;
	for (int i = 0; i < K; i++) {
		cin >> input;
		power_plant[input] = true;
	}

	parent.resize(N + 1);
	for (int i = 1; i < N + 1; i++) {
		parent[i] = i;
	}

	vector<tuple<int, int, int>> costs(M); // cost, from, to
	int u, v, w;
	for (int i = 0; i < M; i++) {
		cin >> u >> v >> w;
		costs[i] = { w, u, v };
	}
	sort(costs.begin(), costs.end());

	int answer = 0, count = 0;
	for (auto t : costs) {
		int cost = get<0>(t);
		int from = get<1>(t);
		int to = get<2>(t);

		if (Find(from) != Find(to) && !(power_plant[parent[from]] && power_plant[parent[to]])) {
			answer += cost;
			Union(from, to);
			count++;
		}

		if (count == N - 1) break;
	}

	cout << answer;

	return 0;
}