[백준(BOJ)] 1197번 : 최소 스패닝 트리 - C++[CPP]

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

1197번: 최소 스패닝 트리

---

⊙ 문제

⊙ 입력

⊙ 출력

⊙ 예제 입출력

⊙ 알고리즘 분류

• 그래프 이론
• 최소 스패닝 트리

 

---

 

⊙ 문제 접근 과정

 

이번에 다뤄볼 문제는 MST 알고리즘이다.

MST는 최소 스패닝 트리로 스패닝 트리 중에서 사용된 간선들의 가중치 합이 최소인 트리를 말한다.

 

MST의 구현 방법에는 Kruskal MST 알고리즘과 Prim MST 알고리즘이 있는데

이번 문제는 Kruskal MST 알고리즘으로 접근해봤다.

 

Kruskal MST 알고리즘의 로직은 아래와 같다.

1. 간선들의 가중치에 대해 오름차순 정렬
2. 가장 낮은 가중치를 선택(그리디 알고리즘)

 

---

 

⊙ 문제 풀이

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <tuple>

#define MAX 10001
using namespace std;

int V, E;
int parent[MAX];
int result=0;
vector<tuple<int,int,int>> v;

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

void connection(int x,int y) {
    x=find(x);
    y=find(y);
    if(x!=y) {
        parent[x]=y;
    }
}

bool same(int x,int y) {
    x=find(x);
    y=find(y);
    if(x==y) return true;
    else return false;
}

int main() {
    cin >> V >> E;

    for(int i=1;i<=V;i++)
        parent[i]=i;

    for(int i=0;i<E;i++) {
        int A,B,C;
        cin >> A >> B >> C;
        v.push_back({C,A,B});
    }

    sort(v.begin(),v.end());

    for(int i=0;i<E;i++) {
        if(!same(get<1>(v[i]), get<2>(v[i]))) {
            connection(get<1>(v[i]), get<2>(v[i]));
            result +=get<0>(v[i]);
        }
    }

    cout << result;
}

---

⊙ 결과

 

---

⊙ 마무리

 

 

트리는 파면 팔 수록 알아야 할게 많다....ㅠ

 

 

좋아요는 로그인하지 않아도 누를 수 있습니다!