8주차(최소신장트리) - [C++]백준1197 최소 스패닝 트리

08 May 2022 in Study on Algorithm

백준1197 최소 스패닝 트리 링크

문제

예제 입력

---

코드

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int arr[10001];
vector<pair<int, pair<int, int>>> vec;

// 원소가 속한 집합 찾기  
int find(int x) {
    if (arr[x] != x) arr[x] = find(arr[x]);
    return arr[x];
}

// 두 원소 집합 합치기  
void Union(int a, int b) {
    a = find(a);
    b = find(b);
    if (a < b) arr[b] = a;
    else arr[a] = b;
}

int main() {
    int v, e;
    cin >> v >> e;
    for (int i = 1; i <= v; i++) arr[i] = i;

    for (int i = 0; i < e; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        vec.push_back({ c, { a, b } });
    }
    sort(vec.begin(), vec.end());

    // 크루스칼 알고리즘 = 간선값이 낮은 것부터 정점을 집합화
    int cost = 0;
    for (int i = 0; i < vec.size(); i++) {
        if (find(vec[i].second.first) != find(vec[i].second.second)) {
            Union(vec[i].second.first, vec[i].second.second);
            cost += vec[i].first;
        }
    }
    cout << cost;
}

설명

이 문제는 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리를 줄여 최소신장트리(MST)의 개념에 대한 것입니다. C++ STL(표준 템플릿 라이브러리)에서 vector를 사용하여 구현했습니다. 그래프에 대한 정보를 입력 받아 서로소 집합에 대한 개념으로 사이클이 생겨서 그래프가 되지 않게 확인해주며 크루스칼 알고리즘으로 간선의 값이 낮은 것부터 정점을 그룹화하여 가중치가 최소인 트리의 결과를 출력합니다.

-pair<자료형, 자료형> 변수명; : 하나의 변수에 2가지 값을 저장함

<algorithm>
-sort(시작, 끝, 비교함수) : 배열의 크기만큼 정렬

<vector>
-vector<자료형> 변수명; : 배열 자료구조 사용

---

결과