백준 16398 - 행성 연결(C++)

문제 링크입니다 https://www.acmicpc.net/problem/16398

16398번: 행성 연결

간단한 MST 문제였습니다. 

문제 조건

출력 예시

플로우 관리비용이 10억까지 있어, long long을 써주는 것만 주의하면 되는 문제였습니다.

 

Union + Find 함수를 이용해 Kruskal 알고리즘을 구현했습니다. -> 이것만 할 수 있으면 푸는 문제입니다

 

자세한 것은 코드를 참고해주세요!

 

#include <iostream>
#include <stdio.h>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cstring>
#include <queue>
#include <vector>
#include <stack>
#include <cmath>
using namespace std;

typedef struct li {
    int start;
    int finish;
    long long int cost;
}li;
vector<li> planet;
int num;
int connect[1001];
long long int cost_min;
int planet_cost[1001][1001];


bool cmp(li a, li b) {
    if (a.cost < b.cost) return true;
    return false;
}

int Find(int x) {
    if (connect[x] == x) return x;
    else return connect[x] = Find(connect[x]);
}

void Union(int x, int y) {
    int xx = Find(x);
    int yy = Find(y);
    connect[xx] = yy;
}

void solve() {
    for (int i = 0; i <= 1000; i++) connect[i] = i;
    for (int i = 0; i < planet.size(); i++) {
        int x = Find(planet[i].start);
        int y = Find(planet[i].finish);
        if (x != y) {
            Union(x, y);
            cost_min += planet[i].cost;
        }
    }
    cout << cost_min;
}

int main()
{
    cin.tie(0);
    cout.tie(0);
    cin >> num;
    for (int i = 0; i < num; i++) {
        for (int j = 0; j < num; j++) {
            cin >> planet_cost[i][j];
        }
    }
    for (int i = 0; i < num; i++) {
        for (int j = i + 1; j < num; j++) {
            planet.push_back({ i + 1,j + 1,planet_cost[i][j] });
        }
    }
    sort(planet.begin(), planet.end(),cmp);
    solve();
    return 0;
}

 

 

질문 및 조언은 댓글 남겨주세요!