[C/C++] 백준 - 1647번 : 도시 분할 계획

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

1647번: 도시 분할 계획

최소 스패닝 트리로 해결 가능한 문제이다.

마을을 2개로 분리하고, 각 마을에는 최소 1개의 집이 존재하여야 한다고 한다.

마을에 2개 이상의 집이 있어야 한다고 하면 문제가 복잡해지는데 이 문제는 1개의 집만 있으면 되기 때문에

최소 길이의 간선으로 각 집을 하나의 마을로 묶어주고, 가장 긴 간선의 길이를 빼서 분리시켜주면 된다.

#include<iostream>
#include<cmath>
#include<list>
#include<stack>
#include<tuple>
#include<cstring>
#include<map>
#include<algorithm>
#include<vector>
#include<deque>
#include<queue>
#define CUNLINK ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define endl '\n'
#define MAX_SIZE 1003
#define INF 0x7fffffff
using namespace std;
typedef long long ll;
typedef struct Information {
	int y, x;
	int Cst;
};

struct cmp {
	bool operator()(Information lhs, Information rhs) {
		return lhs.Cst > rhs.Cst;
	}
};

int N, M;
int Parent[100001];
priority_queue<Information, vector<Information>, cmp> pq;

void Init_Parent(int r) {
	for (int i = 1; i <= r; i++) Parent[i] = i;
}

int getParent(int x) {
	if (x == Parent[x]) return x;
	return Parent[x] = getParent(Parent[x]);
}

void Union(int a, int b) {
	a = getParent(a);
	b = getParent(b);

	if (a != b) {
		if (a < b) Parent[b] = a;
		else Parent[a] = b;
	}
}

bool isSameParent(int a, int b) {
	a = getParent(a);
	b = getParent(b);

	if (a == b) return true;
	return false;
}

int main() {
	CUNLINK;
	cin >> N >> M;
	Init_Parent(N);
	while (M--) {
		int From, To, Cost;
		cin >> From >> To >> Cost;
		pq.push({ From, To, Cost });
	}

	vector<int> Length;
	while (!pq.empty()) {
		Information Temp = pq.top();
		pq.pop();

		if (!isSameParent(Temp.y, Temp.x)) {
			Union(Temp.y, Temp.x);
			Length.push_back(Temp.Cst);
		}
	}
	int Answer = 0;
	for (int i = 0; i < Length.size()-1; i++) Answer += Length[i];
	cout << Answer << endl;

	return 0;
}