[알고리즘] 백준 1647번: 도시 분할 계획 (C++)

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

1647번: 도시 분할 계획

최소 스패닝 트리를 2개 가져야 하는데라고 생각하면 머릿속에 생각되는 트리 2개의 그림 때문에 접근이 어려웠다.

하지만, 문제에서 이 조건을 잘 봐야 한다.

"마을에는 집이 하나 이상 있어야 한다."

이 말은 마을에 집이 하나만 있으면 된다고 말하는 것과 같다. 즉, 최소 스패닝 트리를 구하되 마지막 노드를 포함시키지 않는다면 두 마을이 형성될뿐더러 남아있는 모든 길의 합이 최솟값이 된다.

[AC 코드]

#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#define MAX (100000 + 1)
#define pii pair<int, int>
#define ll long long
using namespace std;

vector<pair<pii, ll>> edges;
int parent[MAX];
int n, m;

bool cmp(pair<pii, int> a, pair<pii, int> b) {
	return a.second < b.second;
}

int getRoot(int node) {
	if (parent[node] == node) {
		return node;
	}
	return parent[node] = getRoot(parent[node]);
}

bool find(int a, int b) {
	if (getRoot(a) == getRoot(b)) {
		return true;
	}
	else return false;
}

void unionParent(int a, int b) {
	if (getRoot(a) < getRoot(b)) {
		parent[getRoot(b)] = getRoot(a);
	}
	else parent[getRoot(a)] = getRoot(b);
}

int main() {
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int a, b, w;
		cin >> a >> b >> w;
		edges.push_back({ {a, b}, w });
	}

	sort(edges.begin(), edges.end(), cmp);
	
	for (int i = 1; i <= n; i++) {
		parent[i] = i;
	}

	int answer = 0;
	int cnt = 0;
	for (int i = 0; i < edges.size(); i++) {
		if (!find(edges[i].first.first, edges[i].first.second)) {
			if (cnt < n - 2) {
				unionParent(edges[i].first.first, edges[i].first.second);
				answer += edges[i].second;
				cnt++;
			}
		}
	}

	cout << answer;
	return 0;
}