[BOJ] 2211번 네트워크 복구 (C++)

문제 (https://www.acmicpc.net/problem/2211)

2211번: 네트워크 복구

처음엔 MST를 사용해야하나? 라는 생각이 들었지만 다익스트라로 만들어진 MST와 MST는 서로 다르다는 반례를 보고 다익스트라로 문제를 해결했다.

 

11779 최소비용 구하기 2 문제에서 사용했던 방식과 유사하다. route라는 배열을 생성하여 배열의 해당 인덱스에 도달하기 위해서는 몇 번에서 와야 하는지를 기록한다.

route[a] = b는 "a번에 최소로 도달하기 위해서는 b번에서 와야 한다"라는 의미

 

네트워크를 복구하기 위해서는 무조건 n-1개의 회선을 복구하면 되므로 첫 번째 출력 값은 n-1이다.

복구할 회선들을 출력하는 경우 2부터 n까지 반복하며 route 배열의 인덱스와 값을 같이 출력해주었다. (즉, route[i], i = 출발 번호, 도착 번호)

---

[소스코드]

	/*
	BOJ 2211번: 네트워크 복구
	DATE: 2022-01-10
	Dijkstra Algorithm
	*/
	#include <iostream>
	#include <vector>
	#include <queue>
	#define MAX 1001
	#define INF 1e9
	using namespace std;
	vector<pair<int,int>> graph[MAX];
	int d[MAX];
	int route[MAX]; // route[a] = b: a번에 최소로 도달하기 위해서는 b 정점에서 와야 한다.
	void dijkstra(int start){
	priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
	pq.push({0, start});
	d[start] = 0;
	while(!pq.empty()){
	int distance = pq.top().first;
	int cur = pq.top().second;
	pq.pop();
	if(d[cur] < distance) continue;
	for(int i = 0 ; i < graph[cur].size() ; i++){
	int newDistance = graph[cur][i].second;
	int next = graph[cur][i].first;
	if(distance + newDistance < d[next]){
	route[next] = cur;
	d[next] = distance + newDistance;
	pq.push({d[next], next});
	}
	}
	}
	}
	int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int n, m;
	int a, b, c;
	cin >> n >> m;
	for(int i = 0 ; i < m ; i++){
	cin >> a >> b >> c;
	graph[a].push_back({b, c});
	graph[b].push_back({a, c});
	}
	fill(d, d + n + 1, INF);
	dijkstra(1);
	cout << n - 1 << '\n';
	for(int i = 2 ; i <= n ; i++) cout << route[i] << " " << i << '\n';
	return 0;
	}

view raw 2211.cpp hosted with ❤ by GitHub

---

2022-01-10

Gold 2

- 그래프 이론

- 다익스트라