[G2] 백준 2211번 네트워크 복구 C++ 다익스트

리뷰

 

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

처음엔 MST로 접근했는데 MST로는 해결이 불가능한 문제인 것 같다.

다익스트라 및 경로 복구 방식을 사용하여 AC를 받았다.

 

 

전역 변수

1. n : 컴퓨터의 개수를 저장할 변수
2. m : 간선의 개수를 저장할 변수
3. Edge : 간선 정보 중 이동할 컴퓨터 번호 next, 가중치 val을 정의할 구조체
4. edges : 간선 정보를 저장할 벡터 배열
5. Info : 시뮬레이션 시 사용할 현재 컴퓨터 번호 cur, 누적 가중치 pre_val을 정의할 구조체, pre_val기준 오름차순 정렬한다.

 

함수

1. dijkstra

void dijkstra()

 

다익스트라를 통해 모든 컴퓨터를 연결하는 최단 경로를 구하고 그 간선 정보를 출력할 함수

1. Info타입의 우선순위 큐 pq를 초기화 하고, 초기값으로 슈퍼 컴퓨터 번호 1과 누적 가중치 0을 push한다.
2. 거리 정보를 저장할 dist벡터를 n + 1크기, 초기값 20억으로 초기화 해준다.
3. 간선 정보를 저장할 path벡터를 n + 1크기, 초기값 0으로 초기화 해준다.
4. 1번 노드의 dist값을 0으로 초기화 한다.
5. pq가 빌 때 까지 whilf루프를 순회하며, 매 루프마다 요소를 한개씩 꺼내어 준다.
6. 현재 컴퓨터의 인접 리스트를 순회하며 더 짧은 경로가 있을 경우 갱신해 준다.
7. 갱신을 할 때 path배열의 이동할 컴퓨터 번호에 현재 컴퓨터 번호의 값을 저장해 준다.
8. while루프가 종료된 후 n - 1을 출력하고 줄 바꿈을 진행해 준다.
9. 추가로 2 ~ n번 컴퓨터를 순회하며 현재 컴퓨터 번호와 path에 저장된 값을 출력 후 줄바꿈을 진행해 준다.

 

문제풀이

1. n, m에 값을 입력 받고, m개의 간선 정보를 edges배열에 양방향으로 추가해 준다.
2. dijkstra 함수를 호출한다.

 

트러블 슈팅

1. 어차피 모든 컴퓨터가 연결되는 최소 비용을 구하는 것이므로 MST를 사용했으나 Fail을 받았다.
2. 다익스트라로 로직을 변경하니 AC를 받았다.

 

참고 사항

• 출력은 임의의 순서대로 하며, 답이 여러 개 존재하는 경우에는 아무 것이나 하나만 출력하면 된다.
• 모든 통신은 완전쌍방향 방식으로 이루어지기 때문에, 한 회선으로 연결된 두 컴퓨터는 어느 방향으로도 통신할 수 있다.

 

정답 코드

#include<iostream>
#include<queue>
#include<vector>
using namespace std;

int n, m;
struct Edge {
	int next, val;
};
vector<Edge> edges[1001];
struct Info {
	int cur, pre_val;
	bool operator<(const Info& other) const {
		return pre_val > other.pre_val;
	}
};

void dijkstra() {
	priority_queue<Info> pq;
	pq.push({ 1, 0 });
	vector<int> dist(n + 1, 2e9);
	vector<int> path(n + 1, 0);
	dist[1] = 0;

	while (!pq.empty()) {
		Info info = pq.top(); pq.pop();
		int cn = info.cur, cd = info.pre_val;
		if (dist[cn] < cd) continue;

		for (const Edge& edge : edges[cn]) {
			int nn = edge.next, nd = edge.val;
			if (dist[nn] > cd + nd) {
				dist[nn] = cd + nd;
				path[nn] = cn;
				pq.push({ nn, cd + nd });
			}
		}
	}

	cout << n - 1 << "\n";
	for (int i = 2; i <= n; ++i) cout << i << " " << path[i] << "\n";
}

int main() {
	cin >> n >> m;
	while (m--) {
		int a, b, c; cin >> a >> b >> c;
		edges[a].push_back({ b, c });
		edges[b].push_back({ a, c });
	}
	dijkstra();
}