baekjoon 1197:최소 스패닝 트리

baekjoon 1197 최소 스패닝 트리

1197번 최소 스패닝 트리

접근

//clrs그림 넣고 설명 들어갈 거임 전형적인 mst 문제이다.
mst알고리즘으로 kruskal 알고리즘을 선택했다. kruskal 알고리즘은 매 선택에서 다른 집합을 잇는 edge중
가장 weight이 작은 edge를 선택한다는 점에서 greedy 알고리즘의 일종이다.
kruskal 알고리즘의 개략적인 순서는 다음과 같다.

1. edge를 weight오름차순기준으로 sort시킨다.
2. weight순서대로 돌면서 그 edge가 서로 다른 집합을 이어주면 연결시킨다.
   집합 연결은 union-find알고리즘으로 한다. 그리고 여기서는 굳이 필요 없을 것 같지만 path compression을 써 주었다.
   kruskal알고리즘에선 정렬하는게 가장 큰 시간 잡아 먹기 때문에 O(ElogE)의 시간 복잡도를 가진다.

코드

//1197
#include <iostream>
#include <vector>
#include <array>
#include <algorithm>
using namespace std;
array<int, 10001> uf;
int find(int a){
  if(uf[a] == a) return a;
  return uf[a] = find(uf[a]);
}
bool merge(int a, int b){
  int rootA = find(a);
  int rootB = find(b);
  if(rootA == rootB) return false;
  uf[rootA] = rootB;
  return true;
}

struct Edge{
  int s, e, w;
  Edge(int s1, int e1, int w1): s(s1), e(e1), w(w1){}
  bool operator<(const Edge& e) const{ return w < e.w;}
};
vector<Edge> edges;
int main(){
  int v, e;
  cin >> v >> e;
  for(int i = 0; i < e; i++){
    int s, e, w; cin >> s >> e >> w;
    edges.push_back(Edge(s, e, w));
  }
  sort(edges.begin(), edges.end());
  for(int i = 1; i <= v; i++) uf[i] = i;
  long long int ans = 0;
  int count = 0;
  for(int i = 0; i < e; i++){
    if(merge(edges[i].s, edges[i].e)){
      ans += (long long int)edges[i].w;
      if(++count == v - 1) break;
    }
  }
  cout << ans << endl;


  return 0;
}

배운 점

kruskal 알고리즘 다시 한번 복습한 느낌이었다. Edge struct 만드는 법, union-find 구현법 다 다시 해보았다.