[백준 16398] 행성 연결

문제 풀이

 

2차원 배열 형태로 입력이 들어오고, 이것을 인접 리스트 그래프로 만든 후 MST 알고리즘 중 하나인 크루스칼 알고리즘을 적용해서 MST 비용을 구하면 되는 문제입니다.

 

다만 주의할 점은 i -> j 로 가는 간선과 j -> i 로 가는 간선이 똑같으므로 중복될 수 있기 때문에,

중복을 방지하기 위해서 따로 check 배열로 막았습니다.

 

또, 간선의 비용이 최대 1억이므로 long long 자료형만 주의해서 구현하면 됩니다.

 

소스 코드

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

int N;
const int MAX = 1001;
int adj[MAX][MAX];
vector<pair<int, pair<int, int> > > edges;
int parent[MAX];
bool check[MAX][MAX];

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

void merge(int a, int b)
{
	a = find(a);
	b = find(b);
	if (a < b) parent[b] = a;
	else parent[a] = b;
}

void kruskal()
{
	sort(edges.begin(), edges.end());
	for (int i = 1; i <= N; i++) parent[i] = i;

	int sz = static_cast<int>(edges.size());
	long long totalCost = 0;
	for (int i = 0; i < sz; i++)
	{
		int cost = edges[i].first;
		int a = edges[i].second.first;
		int b = edges[i].second.second;
		if (find(a) != find(b))
		{
			totalCost += cost;
			merge(a, b);
		}
	}

	cout << totalCost << endl;
}

void input()
{
	cin >> N;
	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= N; j++)
		{
			cin >> adj[i][j];
		}
	}

	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= N; j++)
		{
			if (i == j) continue;
			if (!check[i][j] && !check[j][i])
			{
				check[i][j] = check[j][i] = true;
				edges.push_back({ adj[i][j], {i,j} });
			}
		}
	}
}

void solve()
{
	input();
	kruskal();
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	solve();
	return 0;
}