백준 2211(네트워크 복구)

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

2211번: 네트워크 복구

모든 연결이 끊겨 있는 상태에서 어떤 조건들을 만족하면서 최소의 연결방법을 구하는 문제이다. 

 

어떤 조건을 빼고 보면 최소 스패닝 트리라고 보면 된다. 

 

1부터 시작해서 인접한 곳에서 방문하지 않았던 지점 중 거리가 최소인 지점을 연결한다.  

이 결과는 총 연결 거리의 최소를 만들어 내는 알고리즘이다. 

 

하지만 문제에서 

 

1. 네트워크를 복구해서 통신이 가능하도록 만드는 것도 중요하지만, 해커에게 공격을 받았을 때 보안 패킷을 전송하는 데 걸리는 시간도 중요한 문제가 된다. 따라서 슈퍼컴퓨터가 다른 컴퓨터들과 통신하는데 걸리는 최소 시간이, 원래의 네트워크에서 통신하는데 걸리는 최소 시간보다 커져서는 안 된다.

이렇게 조건이 주어져 있기 때문에 2->3까지의 연결 고리가 단순 최소라고 바로 이어서는 안된다. 

 

1->3 vs 1->2 + 2->3 을 비교해서 1->3 보다 크면 2->3을 연결하면 안된다.  

 

 dist[p2.second.second] < dist[p2.second.first] + p2.first

위 경우라면 문제 조건에 맞지 않으므로 패스

 

그래서 여기에 다익스트라 알고리즘이 추가된다. 

 

플로이드 와샬(모든 정점에서 다른 모든 정점까지 가는 모든 최단거리를 구하는 알고리즘) 을 생각했었지만 

보안 패킷은 1에서 시작하므로 그렇게 구할 필요도 없고, O(N^3) => 10^9이므로 시간초과가 난다. 

 

그래서 한 지점에서 다른 모든 지점까지 가는 다익스트라 알고리즘을 사용했다. 

 

 

먼저 1을 기준으로 최소 지점의 거리와 index를 구한다. 

그 다음 index를 지나면서 1->index + index->특정 지점 vs 1->특정지점을 비교해서 만약 1->특정지점보다 작으면 dist[]배열을 최신화 해준다. 이렇게 모든 지점을 통해서 다른 지점을 확인하고 나면, 1에서 다른 지점으로 가는 최단 거리 배열을 구할 수 있다. 

 

void di_init() {
	for (int i = 2; i <= N; i++) {
		dist[i] = conn[1][i];
		pq.push(make_pair(-dist[i], i));
	}
	while (!pq.empty()) {
		p = pq.top();
		pq.pop();
		if (!check[p.second]) {
			check[p.second] = true;
			for (int i = 2; i <= N; i++) {
				if (check[i] || p.second == i) continue;
				if (dist[i] > dist[p.second] + conn[p.second][i]) {
					dist[i] = dist[p.second] + conn[p.second][i];
					pq.push(make_pair(-dist[i], i));
				}
			}
		}
	}
}

 

그런 다음 dist배열을 토대로 문제 조건 1.에서 말한 조건을 비교하면서 스패닝트리를 만든다. 

 

최소 스패닝 트리 + 문제 조건

 

최소 스패닝 트리와 다익스트라는 모드 priority_queue를 사용했다. 

 

#include<iostream>
#include<queue>
#include<utility>
using namespace std;
#define MAX 1001

priority_queue<pair<int, int> > pq;
priority_queue<pair<int, pair<int, int> > > sol_pq;
queue<pair<int, int> > answer;
pair<int, int> p;
pair<int, pair<int, int> > p2;
int N, M, a, b, c, INF = 987654321;
int visit_num = 0;
int conn[MAX][MAX] = { 0 };
int dist[MAX];
bool visited[MAX] = { false };
bool check[MAX] = { false };


void di_init() {
	for (int i = 2; i <= N; i++) {
		dist[i] = conn[1][i];
		pq.push(make_pair(-dist[i], i));
	}
	while (!pq.empty()) {
		p = pq.top();
		pq.pop();
		if (!check[p.second]) {
			check[p.second] = true;
			for (int i = 2; i <= N; i++) {
				if (check[i] || p.second == i) continue;
				if (dist[i] > dist[p.second] + conn[p.second][i]) {
					dist[i] = dist[p.second] + conn[p.second][i];
					pq.push(make_pair(-dist[i], i));
				}
			}
		}
	}

}

void solve() {
	for (int i = 2; i <= N; i++) {
		sol_pq.push(make_pair(-conn[1][i], make_pair(1, i)));
	}
	while (!sol_pq.empty()) {
		p2 = sol_pq.top();
		sol_pq.pop();
		p2.first = -p2.first;
		if (visited[p2.second.second] || dist[p2.second.second] < dist[p2.second.first] + p2.first) continue;
		visited[p2.second.second] = true;
		visit_num++;
		answer.push(make_pair(p2.second.first, p2.second.second));
		for (int i = 2; i <= N; i++) {
			if (visited[i]) continue;
			sol_pq.push(make_pair(-conn[p2.second.second][i], make_pair(p2.second.second, i)));
		}
	}

}

int main() {
	cin >> N >> M;

	for (int i = 0; i < M; i++) {
		cin >> a >> b >> c;
		conn[a][b] = c;
		conn[b][a] = c;
	}

	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			if (i == j) continue;
			if (conn[i][j] == 0) conn[i][j] = INF;
		}
	}

	di_init();
	solve();
	cout << visit_num << "\n";
	while (!answer.empty()) {
		p = answer.front();
		answer.pop();
		cout << p.first << " " << p.second << "\n";
	}

}