개요

백준 2211번: 네트워크 복구

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

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

접근 방식

1. 최소 회선을 복구하면서 이전 네트워크의 속도와 비슷하게 맞춰야하는 데 문제의 감도 안왔다.

2. 다른 풀이를 찾아보니 1번 노드(슈퍼컴퓨터)를 기준으로 다익스트라를 사용한다.
   다른 노드들로의 최단거리를 저장하면서, 각 거리가 갱신될 때마다
   배열에 두 노드를 저장하고 마지막에 노드들을 저장한 배열을 순회하며 답을 출력하는 방식이였다.

3. 다익스트라 알고리즘이 끝나면 1번 노드에서 각 노드들로 가는 최단 거리를 갱신하며 결국 배열에는 1번노드에서 다른 노드들로 가는 최단거리의 노드들의 간선이 기록된다.

   map<int,int>을 사용해 저장을 했을때 중복없이 갱신되도록 짰다.

   //최단거리로 연결된 노드 저장용 map
   map<int,int> prevNode;

   for (pair<int, int>& p : adj[curNode]) {
   	int nextNode = p.first, nextDist = p.second;
   	if (minDist[nextNode] > minDist[curNode] + nextDist) {
   		minDist[nextNode] = minDist[curNode] + nextDist;
   		pq.push({ minDist[nextNode],nextNode });
   		//새로운 최단거리를 발견해서 갱신할때 두 노드를 map에 저장해줌
   		prevNode[nextNode]=curNode;
   	}
   }

전체코드

#include<iostream>
#include<vector>
#include<map>
#include<queue>

using namespace std;
int N, M;
int INF = 100'000'000;
//네트워크끼리 연결된 가중치
vector<vector<pair<int, int>>> adj;
//최단거리로 연결된 노드 저장용 map
map<int,int> prevNode;
//방문 여부 배열
bool visited[1001];
//최단거리 저장용 배열
int minDist[1001];
//다익스트라 용 우선순위큐 
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

void Input() {
	int tmpNode1, tmpNode2, tmpTime;
	cin >> N >> M;
	adj.resize(N);
	for (int i = 0; i < M; i++) {
		cin >> tmpNode1 >> tmpNode2 >> tmpTime;
		//양 방향이므로 두개 다 push back 
		adj[--tmpNode1].push_back({ --tmpNode2,tmpTime });
		adj[tmpNode2].push_back({tmpNode1,tmpTime });
	}
	
	fill(minDist, minDist + 1000, INF);
	fill(visited, visited + 1000, false);
	minDist[0] = 0;
	pq.push({minDist[0],0});
}
void Solution() {
	int curNode=0;
	while (!pq.empty()) {
		do {
			curNode = pq.top().second;
			pq.pop();
		} while (!pq.empty() && visited[curNode]);

		visited[curNode] = true;
		
		for (pair<int, int>& p : adj[curNode]) {
			int nextNode = p.first, nextDist = p.second;
			if (minDist[nextNode] > minDist[curNode] + nextDist) {
				minDist[nextNode] = minDist[curNode] + nextDist;
				pq.push({ minDist[nextNode],nextNode });
				//새로운 최단거리를 발견해서 갱신할때 두 노드를 map에 저장해줌
				prevNode[nextNode]=curNode;
			}
		}
	}
	//반복문이 끝나고 map에 남은 간선들이 슈퍼컴퓨터에서 다른 노드들과 연결된 최소 간선들이다.

	cout << prevNode.size() << '\n';
	for (auto p : prevNode) {
		cout << p.first+1 << " " << p.second+1<<'\n';
	}
}
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	Input();
	Solution();
}

문풀후생

각 노드의 최단거리가 갱신될때 배열을 통해 저장하는식으로
해당 노드에서 시작노드까지의 최단거리 경로를 저장할수 있다는 개념을 배운 문제다.