[백준 / BOJ] C++ 16398 행성 연결

16398번: 행성 연결

 

문제

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

16398번: 행성 연결

 

 

풀이

입력 행렬이 각 정점 간 간선의 가중치이므로 i행 j열의 값은 i번째 행성과 j번째 행성 간에 플로우를 설치하는 비용이다. 이를 가지고 최소 스패닝 트리(MST)의 가중치를 구하면 된다. 행성의 수가 최대 1,000개이고 각 가중치의 최댓값이 100,000,000 이므로 최소 스패닝 트리의 가중치의 자료형은 long long 이어야 한다.

 

 

코드

#include <bits/stdc++.h>
using namespace std;
#define pii pair<int, int>

int N;
vector<pii> graph[10001];

long long prim() {
  priority_queue<pii> pq;
  vector<int> visited(N + 1, 0);
  visited[1] = 1;
  for (pii edge : graph[1])
    pq.push(edge);
  long long cost = 0;
  while (!pq.empty()) {
    auto [weight, node] = pq.top();
    pq.pop();
    if (!visited[node]) {
      visited[node] = 1;
      cost -= weight;
      for (pii next : graph[node])
        if (!visited[next.second])
          pq.push(next);
    }
  }
  return cost;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cin >> N;
  for (int i = 1; i <= N; i++)
    for (int j = 1; j <= N; j++) {
      int w;
      cin >> w;
      graph[i].push_back({-w, j});
      graph[j].push_back({-w, i});
    }
  cout << prim();
  return 0;
}