백준 2406번, 안정적인 네트워크 풀이

문제

백준 2406번

풀이

최소 스패닝 트리를 구하는 것을 복잡하게 꼬와서 문제에 적어둔 문제입니다.

$ 2, 3, 4, ..., N $번 컴퓨터가 모두 지사의 컴퓨터이고 이 컴퓨터들은 본사 컴퓨터(1번)과 연결되어있는 상태입니다.


문제에서 모든 컴퓨터들이 2개 이상의 간선으로 연결되어야 안정적인 네트워크라고 합니다.

이미 본사 컴퓨터들과는 모두 연결되어 있으니, 본사 컴퓨터를 제외하면 $ 2, 3, 4, ..., N $번 컴퓨터끼리 모두 연결하라는 문제로 볼 수 있습니다.

최소한의 비용으로 $ 2, 3, 4, ..., N $번 컴퓨터를 연결하는 것은 크루스칼 알고리즘을 사용하여 MST를 구하는 문제로 볼 수 있습니다.

 

크루스칼 알고리즘을 돌리는데 $ O(NlogN) $, 정렬을 하는데는 $ O(N^2logN) $이니, 시간 복잡도는 $ O(N^2logN) $이 되겠네요.

소스코드

#include <bits/stdc++.h>

using namespace std;

int UF[1001];

int find(int a) {
	return UF[a] = UF[a] == a ? a : find(UF[a]);
}

int merge(int a, int b) {
	int x = find(a), y = find(b);
	if (x != y) {
		UF[x] = y;
		return 1;
	}
	return 0;
}

struct A {
	int u, v, w;

	bool operator<(const A &other) const {
		return w < other.w;
	}
};

int main() {
	cin.tie(0)->sync_with_stdio(0);
	cout.tie(0);
	int n, m;
	cin >> n >> m;

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

	while (m--) {
		int a, b;
		cin >> a >> b;

		merge(a, b);
	}

	vector<A> vec;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			int w; cin >> w;
			if (i != 1 && j != 1) vec.push_back(A{i, j, w});
		}
	}

	sort(vec.begin(), vec.end());

	int ans = 0;
	vector<pair<int, int>> add;
	for (const auto &a : vec) {
		if (merge(a.u, a.v)) {
			ans += a.w;
			add.emplace_back(a.u, a.v);
		}
	}

	cout << ans << " " << add.size() << "\n";
	for (const auto &a : add) cout << a.first << " " << a.second << "\n";
}