BOJ - 2211번 네트워크 복구, dijkstra(다익스트라) 풀이 (C++)

오늘은 한 정점을 기준으로 모든 노드로 향하는 최단 거리를 구하는데 사용하는 다익스트라 알고리즘을 이용해 백준 2211번 네트워크 복구 문제를 풀이한 과정을 정리해보려 합니다.

BOJ 2211번 네트워크 복구 문제

문제 링크

 

2211번: 네트워크 복구

---

😀 문제 설명

 

N(1 ≤ N ≤ 1,000)개의 컴퓨터로 구성된 네트워크가 있다. 이들 중 몇 개의 컴퓨터들은 서로 네트워크 연결이 되어 있어 서로 다른 두 컴퓨터 간 통신이 가능하도록 되어 있다. 통신을 할 때에는 서로 직접 연결되어 있는 회선을 이용할 수도 있으며, 회선과 다른 컴퓨터를 거쳐서 통신을 할 수도 있다.

각 컴퓨터들과 회선은 그 성능이 차이가 날 수 있다. 따라서 각각의 직접 연결되어 있는 회선을 이용해서 통신을 하는데 걸리는 시간이 서로 다를 수 있다. 심지어는 직접 연결되어 있는 회선이 오히려 더 느려서, 다른 컴퓨터를 통해서 통신을 하는 것이 더 유리할 수도 있다. 직접 연결되어 있는 회선을 사용할 경우에는 그 회선을 이용해서 통신을 하는 데 드는 시간만큼이 들게 된다. 여러 개의 회선을 거치는 경우에는 각 회선을 이용해서 통신을 하는 데 드는 시간의 합만큼의 시간이 걸리게 된다.

어느 날, 해커가 네트워크에 침입하였다. 네트워크의 관리자는 우선 모든 회선과 컴퓨터를 차단한 후, 해커의 공격을 막을 수 있었다. 관리자는 컴퓨터에 보안 시스템을 설치하려 하였는데, 버전 문제로 보안 시스템을 한 대의 슈퍼컴퓨터에만 설치할 수 있었다. 한 컴퓨터가 공격을 받게 되면, 네트워크를 통해 슈퍼컴퓨터에 이 사실이 전달이 되고, 그러면 슈퍼컴퓨터에서는 네트워크를 이용해서 보안 패킷을 전송하는 방식을 사용하기로 하였다. 준비를 마친 뒤, 관리자는 다시 네트워크를 복구하기로 하였다. 이때, 다음의 조건들이 만족되어야 한다.

1. 해커가 다시 공격을 할 우려가 있기 때문에, 최소 개수의 회선만을 복구해야 한다. 물론, 그렇다면 아무 회선도 복구하지 않으면 되겠지만, 이럴 경우 네트워크의 사용에 지장이 생기게 된다. 따라서 네트워크를 복구한 후에 서로 다른 두 컴퓨터 간에 통신이 가능하도록 복구해야 한다.
2. 네트워크를 복구해서 통신이 가능하도록 만드는 것도 중요하지만, 해커에게 공격을 받았을 때 보안 패킷을 전송하는 데 걸리는 시간도 중요한 문제가 된다. 따라서 슈퍼컴퓨터가 다른 컴퓨터들과 통신하는데 걸리는 최소 시간이, 원래의 네트워크에서 통신하는데 걸리는 최소 시간보다 커져서는 안 된다. (최단 경로를 구해야 한다!!)

원래의 네트워크에 대한 정보가 주어졌을 때, 위의 조건을 만족하면서 네트워크를 복구하는 방법을 알아내는 프로그램을 작성하시오.

 

😀입력

 

첫째 줄에 두 정수 N, M이 주어진다. 다음 M개의 줄에는 회선의 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 컴퓨터와 B번 컴퓨터가 통신 시간이 C (1 ≤ C ≤ 10)인 회선으로 연결되어 있다는 의미이다. 컴퓨터들의 번호는 1부터 N까지의 정수이며, 1번 컴퓨터는 보안 시스템을 설치할 슈퍼컴퓨터이다. 모든 통신은 완전쌍방향 방식으로 이루어지기 때문에, 한 회선으로 연결된 두 컴퓨터는 어느 방향으로도 통신할 수 있다.

 

😀 출력

 

첫째 줄에 복구할 회선의 개수 K를 출력한다. 다음 K개의 줄에는 복구한 회선을 나타내는 두 정수 A, B를 출력한다. 이는 A번 컴퓨터와 B번 컴퓨터를 연결하던 회선을 복구한다는 의미이다. 출력은 임의의 순서대로 하며, 답이 여러 개 존재하는 경우에는 아무 것이나 하나만 출력하면 된다.

 

이번 문제는 다익스트라 알고리즘의 기본 코드를 조금만 수정해도 풀 수 있는 어려운듯 쉬운 문제였습니다.

 

다만, 이 문제를 풀기 위해서는 '1'번 노드(컴퓨터)를 기준으로 모든 노드로의 최단 거리를 갱신하며, 최단 거리를 이루는 간선들의 정보를 저장하며 그래프 탐색을 진행한다는 점이 기본 예제와는 차이가 있었던 것 같습니다.

 

이 점을 해결하기 위해서, 코드를 보면 알 수 있겠지만, 최단 거리를 갱신하는 경우 parent 배열을 이용해서 이전에 방문한 노드의 정보를 같이 갱신하도록 구현해서 문제를 해결할 수 있었습니다.

 

추가적으로 n개의 정점을 연결하기 위해서는 n-1개의 간선이 필요하다는 점을 이용해 K값(n-1) 또한 간단하게 구할 수 있습니다!

---

소스 코드 (C++) 😎

/*
	Date: 2022/08/06
	Brief:
	dijkstra
	Reference:
*/
#include <iostream>
#include <vector>
#include <queue>

#define MAX 1001
#define INF 10001

using namespace std;

int n, m;
int d[MAX];
int parent[MAX];
vector<pair<int, int>> v[MAX];


void dijkstra(int x) {
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

	pq.push({0, x});

	for (int i = 2; i <= n; i++) {
		d[i] = INF;
	}
	d[1] = 0;

	while (!pq.empty()) {
		int cur = pq.top().second;
		int dis = pq.top().first;
		pq.pop();

		for (int i = 0; i < v[cur].size(); i++) {
			int next = v[cur][i].first;
			int next_dis = dis + v[cur][i].second;

			if (next_dis >= d[next])
				continue;
			// 최소 거리 갱신하고, 이전에 방문한 노드를 바꿔준다.
			d[next] = next_dis;
			parent[next] = cur;

			pq.push({ next_dis, next });
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n >> m;

	for (int i = 0; i < m; i++) {
		int start, end, distance;
		cin >> start >> end >> distance;

		v[start].push_back({ end, distance });
		v[end].push_back({ start, distance });
	}

	dijkstra(1);
	// n개의 정점을 연결하기 위해서는 n-1개의 간선이 필요하다.
	cout << n - 1 << "\n";

	for (int i = 2; i <= n; i++) {
		cout << parent[i] << " " << i << "\n";
	}

	return 0;
}

/*
key point:
1. dijkstra
2. n개의 정점을 연결하기 위해서 n-1개의 간선만 있으면 된다.
3. 모든 정점으로의 최단 거리를 갱신할 때, 이전에 방문한 노드만 체크하면 된다.
*/