백준 16398번 행성 연결

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

저는 아직 풀지 않았지만 백준에도 유사한 문제가 있는 것으로 알고 있습니다.

전형적인 MST(Minimum Spanning Tree) 알고리즘 문제였고 최소 신장 트리를 구축하는데 드는 최소 비용을 Kruskal 알고리즘을 이용해서 구하면 되는 문제였습니다.

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

 

const int MAX = 1000;

 

int planet[MAX][MAX];

int parent[MAX], ranks[MAX];

 

//부모 찾는 함수

int findParent(int v)

{

        if (v == parent[v])

                 return v;

 

        return parent[v] = findParent(parent[v]);

}

 

//집합 합치는 함수

void merge(int a, int b)

{

        a = findParent(a);

        b = findParent(b);

        if (a != b)

        {

                 if (ranks[a] < ranks[b])

                         swap(a, b);

                 parent[b] = a;

                 if (ranks[a] == ranks[b])

                         ranks[a]++;

        }

}

 

//구조체 선언(정점1, 정점2, 가중치)

struct Edge {

        int u, v, weight;

        bool operator<(Edge const &e)

        {

                 return weight < e.weight;

        }

};

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0);

        int N;

        cin >> N;

 

        //행렬을 입력받고

        for (int i = 0; i < N; i++)

                 for (int j = 0; j < N; j++)

                         cin >> planet[i][j];

 

        vector<Edge> edge;

        //정점1->정점2 혹은 정점2->정점1 간선을 하나만 입력받음

        for (int i = 0; i < N; i++)

                 for (int j = i + 1; j < N; j++)

                         edge.push_back({ i, j, planet[i][j] });

       

        //정렬하고

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

        //초기화

        for (int i = 0; i < N; i++)

        {

                 parent[i] = i;

                 ranks[i] = 0;

        }

        long long result = 0;

        //간선 가중치의 최소값을 구함

        for (int i = 0; i < edge.size(); i++)

        {

                 Edge e = edge[i];

                 if (findParent(e.u) != findParent(e.v))

                 {

                         result += e.weight;

                         merge(e.u, e.v);

                 }

        }

        cout << result << "\n";

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~