백준, boj ) 2211. 네트워크 복구 ( C++)

1. 문제 링크

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

2211번: 네트워크 복구

2. 문제 개요

N개의 컴퓨터로 구성된 네트워크가 있다. 통신을 할 때에는 서로 직접 연결되어 있는 회선을 이용할 수도 있으며, 회선과 다른 컴퓨터를 거쳐서 통신을 할 수도 있다.

 

어느 날 해커가 침입해서 네트워크를 복구해야 하는 상황에 이르렀다. 다음 두 가지 조건을 만족해야 한다.

(1). 최소 개수의 회선만을 복구해야 한다. 네트워크를 복구한 후에 서로 다른 두 컴퓨터간에 통신이 가능하도록 복구해야한다.

(2). 슈퍼컴퓨터가 다른 컴퓨터들과 통신하는데 걸리는 최소 시간이 원래의 네트워크에서  통신하는데 걸리는 최소 시간보다 커져서는 안 된다.

 

3. 문제 힌트

조건을 잘 생각해 보자.

(1)에 의해서 Spanning Tree를 구하면 된다. 그런데 이게 '최소'스패닝 트리랑은 개념이 다르다는 것을 유의하자.

결국, '서로 다른 두 컴퓨터 간에 통신이 가능하도록 구현해야 한다.'라고 하는 것은 모든 노드가 '직접'은 연결될 필요가 없고 간접적으로나마 모두 연결되어있어야 하는 것을 의미한다.

 

(2)에 의해서 이문제가 MST문제가 아닌 Dijkstra문제가 됨을 의미한다. 

백준 질문란에 있었던 예제

위의 그림처럼 빨간색은 MST, 초록색은 1(슈퍼컴퓨터)로 시작한 최단거리 경로이다.

이 문제는 1(슈퍼컴퓨터)에서 출발한 패킷의 최단시간을 고려한 스패닝 트리를 구해야 하므로, Dijkstra를 사용한 최단경로가 된다.

 

예를 들어서 초록색인 Dijkstra는 3번까지 패킷이 도달하는데 3, 하지만 MST는 3+2+2 = 7이 걸리게 된다. 따라서 (2) 번 규칙에 위배된다.

 

4. 문제 풀이

우선순위 큐를 사용해서 Dijkstra알고리즘을 구현해주면 된다.

특별한 부분은 경로를 기억하고 있어야 한다는 점인데, 

최단거리를 갱신해줄 때, 그때의 부모(이전 경로)를 설정해주면 된다.

 

뭐 특별하게 우선순위 큐에 계속 경로를 담아가면서 할 필요는 없다.

 

5. 코드

#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <functional>
#define INF 987654321
using namespace std;


vector<vector<pair<int, int>>> adj;
vector<int> dist,route;
priority_queue<pair<int, int>,vector<pair<int, int>>, greater<pair<int, int>>> pq;
int n, m;

int main()
{
	scanf("%d %d", &n, &m);
	adj.resize(n + 1);
	dist.resize(n + 1);
	route.resize(n + 1);

	for (int i = 0; i < m; ++i) {
		int from, to, val;
		scanf("%d %d %d", &from, &to, &val);
		//양방향
		adj[from].push_back({ to,val });
		adj[to].push_back({ from,val });
	}

	fill(dist.begin(), dist.end(), INF);
	//dist, start
	pq.push({0,1});
	dist[1] = 0;
	route[1] = 0;

	while (!pq.empty()) {
		int curd = pq.top().first;	//idx까지 가는데 예상하는 최단거리
		int idx = pq.top().second;	//다음 좌표 
		pq.pop();

		if (dist[idx] < curd)	continue;	//idx까지 가는데 실제 최단거리 < 예상하는 최단거리 라면, continue

		//최단거리 갱신
		//idx를 최단거리 group에 속하게 하는것과 동일

		for (int i = 0; i < adj[idx].size(); ++i) {
			int d = adj[idx][i].second;
			int next = adj[idx][i].first;

			if (dist[next] > d + dist[idx]) {
				dist[next] = d + dist[idx];	//idx -> next 거리가 최단거리라고 가정
				route[next] = idx;	//idx-> next로 가는걸 최단거리라고 가정했으니 이전 노드 설정,
				pq.push({ dist[next],next });	//최단거리의 후보들을 queue에.
			}
		}
	}

	printf("%d\n",n-1);

	for (int i = 2; i <=n; ++i) 
		printf("%d %d\n", route[i], i);
		

	return 0;
}

6. 결과

 

댓글, 지적 환영입니다. :)