문제 푼 날짜 : 2021-09-27

문제

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

접근 및 풀이

최소 스패닝 트리(MST)를 만드는 문제였다.
MST를 만드는 대표적인 알고리즘 중 크루스칼 알고리즘을 적용하여 풀었다.

코드

// 백준 1197번 : 최소 스패닝 트리
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<vector<int>> v;

bool cmp(vector<int> v1, vector<int> v2) {
    return v1[2] < v2[2];
}

int getParent(int parent[], int x) {
    if (parent[x] == x) {
        return x;
    }
    return parent[x] = getParent(parent, parent[x]);
}

bool Find(int parent[], int a, int b) {
    a = getParent(parent, a);
    b = getParent(parent, b);

    if (a == b) {
        return true;
    } else {
        return false;
    }
}

void Union(int parent[], int a, int b) {
    a = getParent(parent, a);
    b = getParent(parent, b);

    if (a < b) {
        parent[a] = b;
    } else {
        parent[b] = a;
    }
}

int main() {
    int V, E, ans = 0;
    cin >> V >> E;

    for (int i = 0; i < E; i++) {
        vector<int> tmp(3);
        cin >> tmp[0] >> tmp[1] >> tmp[2];
        v.push_back(tmp);
    }
    sort(v.begin(), v.end(), cmp);

    int parent[10001];

    for (int i = 0; i <= V; i++) {
        parent[i] = i;
    }
    for (auto c : v) {
        if (Find(parent, c[0], c[1]) == false) {
            ans += c[2];
            Union(parent, c[0], c[1]);
        }
    }

    cout << ans;
    return 0;
}

결과

피드백

가끔가다가 최소 스패닝 트리를 만드는 문제가 나오기도 하는데 프림, 크루스칼 알고리즘을 숙지해둬야겠다.