BOJ (C/C++) 2211번: 네트워크 복구

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

2211번: 네트워크 복구

 

---

풀이

다익스트라를 이용하여 컴퓨터 간의 최소 연결 시간을 찾는다.이 때 현재 노드의 직전 노드를 같이 저장하며 경로 또한 같이 저장한다.

 

구한 경로들을 역추적하며 복구할 라인을 찾는다. 이 때, set에 저장하여 중복되는 경로는 제거한다.

+ 예제의 1-4의 경우 1-2,2-4를 거치는데 이는 1-2까지의 최단거리+2-4의 최단거리이다.

이는 중간에 많은 경로가 존재해도 모두 1~중간 노드의 최단 거리 경로이므로 이미 중간 노드에 저장되어 있다. 따라서 각 노드에서 바로 전에 거쳐 오는 노드와의 경로만 출력해도 정답이다.

또한 모든 컴퓨터를 연결하는 라인의 최소 개수는 노드가 n개일 때 n-1개이다.

 

---

코드

#include <stdio.h>
#include <vector>
#include <queue>
#include <set>
#include <algorithm>
using namespace std;

#define LIMITS 100000000
vector <pair<int, int>> V[50001];

int line[1001][2];
bool visited[1001];

void Recover(int start, int n) {
	set <pair<int, int>> L; // 복구할 line

	int before;
	for (int i = 2; i <= n; i++) {
		int before = i;
		
		// 라인을 역추적하며 경로에 있는 라인들을 저장, set을 사용하여 중복 제거
		while (line[before][1] != start) {
			L.insert({ line[before][1], before });
			before = line[before][1];			
		}
		L.insert({ line[before][1], before });
	}

	// print
	printf("%d\n", L.size());
	for (auto i : L) printf("%d %d\n", i.first, i.second);
}

void Com(int start, int n) {
	priority_queue <pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>> > pq;

	// start point
	line[start][0] = line[start][1]= 0;
	pq.push({ line[start][0], start });

	// 최소 시간 -> Dijkstra
	while (!pq.empty()) {
		int now = pq.top().second, now_s = pq.top().first;
		pq.pop();
		visited[now] = true;

		// 현재 저장된 값이 큐에 저장됐던 값보다 작을 경우 실행 x
		if (line[now][0] < now_s) continue;

		for (int i = 0; i < V[now].size(); i++) {
			int next = V[now][i].first, next_s = V[now][i].second;

			if (visited[next]) continue;

			if (line[next][0] > now_s + next_s) {

				// 최소 비용 갱신과 루트 저장
				line[next][0] = now_s + next_s;
				line[next][1] = now;
				pq.push({ line[next][0], next });
			}
		}
	}
}
int main() {
	int n, m;
	int a, b, c;

	// input
	scanf("%d %d", &n, &m);
	for (int i = 0; i < m; i++) {
		scanf("%d %d %d", &a, &b, &c);
		V[a].push_back({ b, c });
		V[b].push_back({ a, c });
	}

	// Search
	fill(line[0], line[n + 1], LIMITS);
	Com(1, n);
	Recover(1, n);

	return 0;
}

---

+ 코드 2 (recovery 함수 부분만 다름)

#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

#define LIMITS 100000000
vector <pair<int, int>> V[50001];

int line[1001][2];
bool visited[1001];

void Recover(int start, int n) {
	printf("%d\n", n - 1);
	for (int i = 2; i <= n; i++) printf("%d %d\n", line[i][1], i);
}

void Com(int start, int n) {
	priority_queue <pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>> > pq;

	// start point
	line[start][0] = line[start][1]= 0;
	pq.push({ line[start][0], start });

	// 최소 시간 -> Dijkstra
	while (!pq.empty()) {
		int now = pq.top().second, now_s = pq.top().first;
		pq.pop();
		visited[now] = true;

		// 현재 저장된 값이 큐에 저장됐던 값보다 작을 경우 실행 x
		if (line[now][0] < now_s) continue;

		for (int i = 0; i < V[now].size(); i++) {
			int next = V[now][i].first, next_s = V[now][i].second;

			if (visited[next]) continue;

			if (line[next][0] > now_s + next_s) {

				// 최소 비용 갱신과 루트 저장
				line[next][0] = now_s + next_s;
				line[next][1] = now;
				pq.push({ line[next][0], next });
			}
		}
	}
}
int main() {
	int n, m;
	int a, b, c;

	// input
	scanf("%d %d", &n, &m);
	for (int i = 0; i < m; i++) {
		scanf("%d %d %d", &a, &b, &c);
		V[a].push_back({ b, c });
		V[b].push_back({ a, c });
	}

	// Search
	fill(line[0], line[n + 1], LIMITS);
	Com(1, n);
	Recover(1, n);

	return 0;
}