[백준 / BOJ] C++ 1197 최소 스패닝 트리

1197번: 최소 스패닝 트리

 

문제

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

1197번: 최소 스패닝 트리

 

 

풀이

최소 신장 트리(Minimun Spanning Tree, MST)의 개념을 알고 있으면 풀 수 있는 standard 문제다. 최소 스패닝 트리는 주어진 정점을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소가 되는 트리다. 우선순위 큐를 사용하는 프림 알고리즘과 크루스칼 알고리즘으로 구현한 MST 알고리즘을 사용했다.

 

 

코드(프림 알고리즘 - Prim)

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

int V, E;
vector<pii> graph[10001];

int prim() {
  priority_queue<pii> pq;
  vector<int> visited(V + 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 >> V >> E;
  while (E--) {
    int a, b, c;
    cin >> a >> b >> c;
    graph[a].push_back({-c, b});
    graph[b].push_back({-c, a});
  }
  cout << prim();
  return 0;
}

 

 

코드(크루스칼 알고리즘 - Kruskal)

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

int V, E, ans = 0;
vector<pair<int, pair<int, int>>> edge;
vector<int> p;

int find(int x) {
  if (p[x] != x)
    p[x] = find(p[x]);
  return p[x];
}

void merge(int x, int y) {
  x = find(x);
  y = find(y);
  if (x < y)
    p[y] = x;
  else
    p[x] = y;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cin >> V >> E;
  p.resize(V + 1);
  iota(p.begin(), p.end(), 0);
  while (E--) {
    int u, v, w;
    cin >> u >> v >> w;
    edge.push_back({w, {u, v}});
  }
  sort(edge.begin(), edge.end());
  for (auto [weight, path] : edge)
    if (find(path.first) != find(path.second)) {
      ans += weight;
      merge(path.first, path.second);
    }
  cout << ans;
  return 0;
}