[알고리즘] 백준 16398번: 행성 연결 (C++)

https://www.acmicpc.net/problem/16398

16398번: 행성 연결

플로우 전체의 최소 비용을 구하는 문제다.

입력만 행렬의 형태로 들어올 뿐, 최소 스패닝 문제였다.

다만, 입력 과정에서 어차피 양방향이라 주석된 부분처럼 i가 j보다 크거나 같은 경우는 틀렸다고 했었다.

>> 이유를 파악하지 못하고 있다..

>> 최소 스패닝 트리에서는 방향이 의미 없지 않나..?

for (int i = 1; i <= n; i++) {
	for (int j = 1; j <= n; j++) {
		//if (i >= j) continue;
		int value;
		cin >> value;
		edge.push_back({ {i, j}, value });
	}
}

 

[AC 코드]

#include <iostream>
#include <vector>
#include <algorithm>
#define ll long long
#define MAX (1000 + 1)
#define pii pair<int, int>
using namespace std;

vector<pair<pii, ll>> edge;
int parent[MAX];
int n;

bool cmp(pair<pii, ll> a, pair<pii, ll> b) {
	return a.second < b.second;
}

int getRoot(int node) {
	if (node == parent[node]) return node;
	return parent[node] = getRoot(parent[node]);
}

bool find(int a, int b) {
	int rA = getRoot(a);
	int rB = getRoot(b);

	if (rA != rB) return true;
	else return false;
}

void unionParent(int a, int b) {
	int rA = getRoot(a);
	int rB = getRoot(b);
	if (rA < rB) {
		parent[rB] = rA;
	}
	else {
		parent[rA] = rB;
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> n;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			//if (i >= j) continue;
			int value;
			cin >> value;
			edge.push_back({ {i, j}, value });
		}
	}

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

	for (int i = 1; i <= n; i++) {
		parent[i] = i;
	}

	ll sum = 0;
	for (int i = 0; i < edge.size(); i++) {
		if (find(edge[i].first.first, edge[i].first.second)) {
			unionParent(edge[i].first.first, edge[i].first.second);
			sum += edge[i].second;
		}
	}

	cout << sum;
	return 0;
}