[백준 / BOJ] C++ 2211 네트워크 복구

2211번: 네트워크 복구

 

문제

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

2211번: 네트워크 복구

 

 

풀이

1번 정점의 슈퍼컴퓨터에서 모든 정점에 이어야 하므로 최소 시간에 연결이 돼야 하므로 다익스트라 알고리즘으로 풀 수 있다. 다익스트라 알고리즘에 대해 잘 모른다면 아래 링크를 통해 알아보자.

[다익스트라 알고리즘 알아보기]

 

문제에서 요구하는 것은 이어야 하는 간선의 수와 그 간선이다. 따라서 -1로 초기화되어 있는 prev 배열을 만들어 이전 정점의 위치를 기록한다. prev 배열은 각 index(정점)가 어느 정점과 이어져있는지가 기록되어 있는 배열이므로 index 그 index의 값을 모두 출력하면 된다.

 

코드

#include <bits/stdc++.h>
using namespace std;

#define INF 2147483647

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  int N, M;
  vector<pair<int, int>> graph[1001];
  vector<int> dist(1001, INF), visited(1001, 0), prev(1001, -1);
  priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
  cin >> N >> M;
  // 간선
  while (M--) {
    int a, b, c;
    cin >> a >> b >> c;
    graph[a].push_back({b, c});
    graph[b].push_back({a, c});
  }
  // 다익스트라
  dist[1] = 0; // 시작점 1번 정점
  pq.push({0, 1});
  while (!pq.empty()) {
    int curr;
    do {
      curr = pq.top().second;
      pq.pop();
    } while (!pq.empty() && visited[curr]);
    if (visited[curr])
      break;
    visited[curr] = 1;
    for (auto &p : graph[curr]) {
      int next = p.first, d = p.second;
      if (dist[next] > dist[curr] + d) {
        dist[next] = dist[curr] + d;
        prev[next] = curr; // 이전 정점 기록
        pq.push({dist[next], next});
      }
    }
  }
  int cnt = 0;
  // 이어야할 간선 수
  for (int i = 1; i <= N; i++)
    if (prev[i] != -1)
      cnt++;
  cout << cnt << '\n';
  // 이어야할 간선
  for (int i = 2; i <= N; i++)
    cout << i << ' ' << prev[i] << '\n';
  return 0;
}