백준 알고리즘 1197번 : 최소 스패닝 트리

링크

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

문제

그래프가 주어졌을 때, 그 그래프의 최소 스패닝 트리를 구하는 프로그램을 작성하시오.

최소 스패닝 트리는, 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리를 말한다.

입력

첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 가중치 C인 간선으로 연결되어 있다는 의미이다. C는 음수일 수도 있으며, 절댓값이 1,000,000을 넘지 않는다.

그래프의 정점은 1번부터 V번까지 번호가 매겨져 있고, 임의의 두 정점 사이에 경로가 있다. 최소 스패닝 트리의 가중치가 -2,147,483,648보다 크거나 같고, 2,147,483,647보다 작거나 같은 데이터만 입력으로 주어진다.

출력

첫째 줄에 최소 스패닝 트리의 가중치를 출력한다.

예제 입력 및 출력

풀이 코드(C++)

#include <bits/stdc++.h>
#define X first
#define Y second
#define pb push_back
#define MAX 100001
#define INF 1e9+7
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;
using ll = long long;
using ull = unsigned long long;
using dbl = double;
using ldb = long double;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using vi = vector<int>;
#define sz(a) int((a).size())

int root[MAX];

void init(int n){
  for(int i = 0; i <= n; i++) root[i] = i;
}

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

bool Union(int x,int y){
  x = find(x), y = find(y);
  if(x == y) return false;
  root[x] = y;
  return true;
}

struct Edge{
  int u,v,w;
  Edge(): Edge(-1, -1, 0){}
  Edge(int u1,int v1, int w1): u(u1),v(v1),w(w1){}
  bool operator < (const Edge& O)const{ return w < O.w; };
};

int main(){
  fastio;
  int n,m; cin >> n >> m;
  Edge e[MAX];
  init(n);
  for(int i = 0; i < m; i++){
    int a,b,c; cin >> a >> b >> c;
    e[i] = Edge(a-1,b-1,c);
  }
  sort(e, e + m); // 간선을 가중치를 기준으로 오름차순 정렬
  // result : 가중치 합, cnt : 뽑은 간선의 수
  int result = 0, cnt = 0;
  for(int i = 0; ; i++){
    if(Union(e[i].u, e[i].v)){
      result += e[i].w;
      if(++cnt == n - 1) break; // n - 1개의 간선을 뽑으면 나감.(MST)의 조건
    }
  }
  cout << result;
  return 0;
}