[백준 / BOJ] C++ 1922 네트워크 연결

1922번: 네트워크 연결

 

문제

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

1922번: 네트워크 연결

 

 

풀이

기본적인 최소 신장 트리(Minimun Spanning Tree, MST)를 사용하는 문제다. 프림 알고리즘으로 구현하는 MST 알고리즘을 사용했다. MST 알고리즘은 아래 글을 보고 공부했다. 아직 유니온 파인드를 모르기 때문에 크루스칼 알고리즘은 보류해놨다.

https://4legs-study.tistory.com/112

최소 스패닝 트리 (MST) : 프림 알고리즘 (Prim Algorithm)

 

 

코드

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

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

int prim() {
  priority_queue<pii> pq;
  vector<int> visited(N + 1, 0);
  visited[1] = 1;
  for (pii edge : graph[1])
    pq.push(edge);
  int cost = 0;
  while (!pq.empty()) {
    int weight = -pq.top().first;
    int node = pq.top().second;
    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 >> M;
  while (M--) {
    int a, b, c;
    cin >> a >> b >> c;
    graph[a].push_back({-c, b});
    graph[b].push_back({-c, a});
  }
  cout << prim();
  return 0;
}