1197번 최소 스패닝 트리 | Kruskal Algorithm 쿠르스칼 알고리즘 | Baekjoon BOJ 백준 9372 C++ 코드, 해설, 풀이

 

 

이번 포스팅은 백준 1197번 최소 스패닝 트리입니다.

아래 url를 클릭하시면 백준 사이트에서 문제를 볼 수 있습니다.

www.acmicpc.net/problem/1197

1197번: 최소 스패닝 트리

 

 

 

기본 알고리즘

MST 최소 신장 트리 

Kruskal Algorithm 사용

 

참고 설명

line 16
parent[i]가 -1이면 정점 i는 정점 집합의 루트가 됨. 아니면 이 정점은 다른 정점이 루트가 되는 집합에 속한 원소임.

line 43
const로 정의해야 하는 이유
2021/01/13 - [[TROUBLESHOOTING]] - C++ 개체에 멤버 함수과(와) 호환되지 않는 형식 한정자가 있습니다.

line 48-50, 81
vector를 클래스의 변수 기준으로 정렬
2021/01/13 - [[C , C++]] - C++ vector sort() 벡터 클래스 변수 기준 정렬

 

 

 

 

전체 코드

//백준1197 최소스패닝트리
 
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define MAX_VTXS 10000
 
class VertexSets { //정점 집합 클래스
    int parent[MAX_VTXS]; //부모 정점의 id
    int nSets;            //집합의 개수
 
public:
    VertexSets(int n) :nSets(n) {
        for (int i = 0; i < nSets; i++)
            parent[i] = -1; //모든 정점이 고유의 집합에 속함
    }
    
    bool isRoot(int i) {
        return parent[i] < 0;
    }
 
    int findSet(int v) { //전체 집합들 중에서 정점 v를 포함하는 집합의 루트를 찾아서 반환
        while (!isRoot(v)) { //v가 어떤 집합의 루트가 아니면 계속 루트를 찾아감
            v = parent[v];
        }     
        return v;
    }
 
    void unionSets(int s1, int s2) { //두 집합 s1, s2 합하는 함수
        parent[s1] = s2; //parent[s1]이 s2를 가리키도록 함. s1은 더 이상 루트가 아님.
        nSets--;
    }
 
};
 
class Edge {
    int v1;
    int v2;
    int w;
public:
    Edge(int ver1, int ver2, int weight): v1(ver1), v2(ver2), w(weight) {}
    int getWeight() const { return w; }
    int getV1() { return v1; }
    int getV2() { return v2; }
};
 
bool compareWeight(const Edge& n1, const Edge& n2) {
    return n1.getWeight() < n2.getWeight();
}
 
int V, E;
vector<Edge> eVec; //간선 저장 벡터
 
void Kruskal() {
    int sum = 0;
 
    VertexSets set(V); //정점 개수만큼 초기 집합 생성
    for (int i = 0; i < E; i++) {
        int uSet = set.findSet(eVec[i].getV1());
        int vSet = set.findSet(eVec[i].getV2());
 
        if (uSet != vSet) {
            sum += eVec[i].getWeight(); //가중치 합
            set.unionSets(uSet, vSet);
        }
    }
 
    cout << sum << endl;
}
 
int main() {
    cin >> V >> E;
 
    int A, B, C;
    for (int i = 0; i < E; i++) {
        cin >> A >> B >> C;
        eVec.push_back(Edge(A, B, C));
    }
 
    sort(eVec.begin(), eVec.end(), compareWeight);
 
    Kruskal();
}