[C++] 백준 2211번: 네트워크 복구

문제 링크

2211번: 네트워크 복구

문제 요약

1번 컴퓨터와 모든 정점이 최소 갯수의 간선으로 연결된 그래프의 간선을 모두 출력해야 한다. 이때, 1번 정점에서 각 정점으로 가는 경로의 길이는 기존 그래프보다 길어선 안된다.

접근 방법

그래프의 N개의 정점을 최소 간선으로 연결하기 위해서는 트리 형태여야 합니다. 트리의 간선의 수는 N - 1개 입니다. 최소 스패닝 트리를 떠올리기 쉽지만, 두번째 조건으로 인해서 단순 최소 스패닝 트리로는 풀리지 않습니다.

1번 정점에서 각 정점으로 가는 다익스트라 알고리즘을 돌리면서, 경로 역추적을 하는 것처럼 현재 정점이 어디서 왔는지를 기록해둡니다. 그리고 그 간선들을 모두 출력해주면 됩니다.

코드

#include <bits/stdc++.h>

using namespace std;

const int MAX = 1001, INF = 1e9;
int dist[MAX], parent[MAX];
vector<pair<int, int>> adj[MAX];

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

	int n, m;
	cin >> n >> m;

	for (int i = 0; i < m; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		adj[a].push_back({ b, c });
		adj[b].push_back({ a, c });
	}

	fill_n(dist, MAX, 1e9);
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
	pq.push({ 0, 1 });

	while (!pq.empty()) {
		auto now = pq.top();
		pq.pop();

		if (now.first > dist[now.second])
			continue;

		for (auto& next : adj[now.second]) {
			if (now.first + next.second < dist[next.first]) {
				dist[next.first] = now.first + next.second;
				parent[next.first] = now.second;
				pq.push({ dist[next.first], next.first });
			}
		}
	}

	cout << n - 1 << '\n';
	for (int i = 2; i <= n; i++)
		cout << i << ' ' << parent[i] << '\n';
	return 0;
}