백준 1197 최소 스패닝 트리 쉬운 풀이(C++/CPP)

문제링크 : https://www.acmicpc.net/problem/1197

문제 접근

• 최소 스패닝 트리 기본 문제
• 개념 참조 : https://dev-jango.tistory.com/22

시간복잡도 계산

• 최소스패닝트리 Kruscal : O(ElgE)

코드

• Kruscal로 해결

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69

#include <iostream> #include <tuple> #include <algorithm>   using namespace std; typedef tuple<int, int, int> ti3;   int p[10010]; ti3 edge[100010];   int find(int v) {     if(p[v] < 0) return v;     return p[v] = find(p[v]); }   // union find bool is_diff_group(int v1, int v2) {     // 각 부모노드를 찾음     v1 = find(v1); v2 = find(v2);          // 부모가 같은 노드라면 종료     if(v1==v2) return 0;          if(p[v1] == p[v2]) p[v1]--;     if(p[v1] < p[v2]) p[v2] =v1;     else p[v1] = v2;     return 1;           }   int main() {     ios::sync_with_stdio(0);     cin.tie(0);          int V,E; cin >> V >> E;     fill(p, p+10010, -1);          // E개의 간선 추가     for(int i=0; i<E; i++) {         int a,b,c; cin >> a >> b >> c;         edge[i] = {c,a,b};     }     sort(edge, edge+E);          int cnt=1;     int ans=0;     for(int i=0; i<E; i++) {         int a,b,c; tie(c,a,b) = edge[i];                  // 둘이 같은 그룹이라면 건너뜀         if(!is_diff_group(a,b)) continue;                  // 다른그룹이라면         cnt++;         ans+=c;                  // 모든 노드 추가되면 종료         if(cnt == V) break;              }          cout << ans << '\n';                    return 0; }   Colored by Color Scripter

cs

문제유형

• 최소 스패닝 트리