[C/C++] 백준 - 2406번 : 안정적인 네트워크

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

2406번: 안정적인 네트워크

문제

한 회사는 본사와 지사의 컴퓨터들을 연결하는 네트워크 시설을 보유하고 있다. 각 지사에는 네트워크용 컴퓨터가 한 대씩 있으며, 이들은 본사의 메인 컴퓨터와 직접 연결되어 있다. 몇몇 지사들끼리 연결되어 있는 경우도 있다.

네트워크 시설에서는 두 컴퓨터가 직접 연결되어 있지 않더라도 다른 컴퓨터들을 경유하여 연결될 수 있다. 예를 들어 1, 2번 컴퓨터가 직접 연결되어 있고, 1, 3번 컴퓨터가 직접 연결되어 있다면, 이것은 2, 3번 컴퓨터가 연결되어 있는 효과도 발휘한다는 것이다.

회사 측에서는 네트워크에 고장이 발생하더라도 컴퓨터들이 연결되어 있도록 안정적인 네트워크를 구축하고자 한다. 네트워크에 고장이 발생하는 경우는 두 가지가 있다. 첫 번째는 직접 연결되어 있는 두 컴퓨터의 연결이 끊어지는 경우이다. 회사 측은 이런 경우에도 이 두 컴퓨터가 다른 컴퓨터들을 경유하여 연결되어 있기를 원한다. 두 번째는 컴퓨터가 고장 나는 경우이다. 회사 측은 이런 경우에는 고장 나지 않은 컴퓨터들끼리 연결되어 있기를 원한다.

예제로 주어진 입력에서 1, 2번 컴퓨터의 연결이 끊어지더라도, 이 두 컴퓨터는 3번 컴퓨터를 통해서 연결되게 된다. 하지만 1번 컴퓨터가 고장 나는 경우에는 5번 컴퓨터가 다른 컴퓨터들과 연결되어 있지 못하게 된다. 따라서 5번 컴퓨터를 다른 컴퓨터와 직접 연결해 주어야 한다.

두 컴퓨터를 연결하는 데 소요되는 비용은 일정하지 않다. 당신은 네트워크의 연결 상태를 입력받아 이 네트워크가 안정적인 네트워크인지 판별하고, 만약 아닐 경우에는 최소 비용으로 회사의 네트워크가 안정적이 되도록 하여야 한다.

 

1번(본사 컴퓨터)와는 모두 연결되어있다고 가정하는 것이기 때문에 1번을 제외한 나머지 컴퓨터들 중 연결이 되어있지않은 컴퓨터들을 연결시키는 최소 비용을 구하면 되는 문제이다.

 

즉, 최소 스패닝 트리 알고리즘 중 크루스칼 알고리즘을 사용하여 해결가능하다.

 

#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <set>
#include <map> 
#define fastio ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define ENDL cout << endl
#define ll long long	
#define ull unsigned long long
#define INF 987654321
#define Mod 1000000
#define endl '\n'
#define pil pair<int,int>

using namespace std;

int N, M;
int parent[1003];
int dist[1003][1003];
priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>> pq;

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

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

bool isSame(int p, int q) {
	p = getParent(p);
	q = getParent(q);

	if (p == q) return true;
	return false;
}

void nodeUnion(int p, int q) {
	p = getParent(p);
	q = getParent(q);

	if (p < q) parent[q] = p;
	else parent[p] = q;
}

void input() {
	cin >> N >> M;
	init_Parent(N);
	for (int i = 0; i < M; i++) {
		int x, y; cin >> x >> y;
		nodeUnion(x, y);
	}

	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			cin >> dist[i][j];
			if (dist[i][j] != 0 && i < j && !isSame(i, j)) {
				pq.push({ -dist[i][j], {i, j} });
			}
		}
	}
}


void solution() {
	int X = 0, K = 0;
	vector<pair<int, int>> answer;
	while (!pq.empty()) {
		pair<int, pair<int, int>> temp = pq.top();
		pq.pop();

		if (isSame(temp.second.first, temp.second.second)) continue;
		if (temp.second.first == 1 || temp.second.second == 1) continue;
		X += temp.first * -1;
		K += 1;

		nodeUnion(temp.second.first, temp.second.second);
		answer.push_back({ temp.second.first,temp.second.second });
	}
	cout << X << " " << K << endl;
	for (auto& ptr : answer) cout << ptr.first << " " << ptr.second << endl;
}

int main() {
	fastio;
	input();
	solution();
	 
	return 0;
}