백준 16398

이 문제는 유니온 파인드 문제이다 이전 게시글에 크루스칼 알고리즘을 사용하면 쉽게 풀린다

#include <iostream>
#include <queue>
using namespace  std;
int n;
int parent[1000];
priority_queue < pair<long long , pair<int, int >> , vector < pair<long long, pair<int, int>>>, greater<pair<long long, pair<int, int>>> > inputData;

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

void uni(int x, int y) {
	int parentX = findParent(x);
	int parentY = findParent(y);
	parent[parentY] = parentX;
}

bool isSameParent(int x, int y) {
	int parentX = findParent(x);
	int parentY = findParent(y);
	if (parentX == parentY)
		return true;
	else
		return false;
}

int main() {
	cin >> n;
	int tmp;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> tmp;
			if (i == j)
				continue;
			inputData.push({ tmp,{i,j} });
		}
	}
	for (int i = 0; i < n; i++) {
		parent[i] = i;
	}
	long long ans = 0;
	while (!inputData.empty()) {
		int from = inputData.top().second.first;
		int to = inputData.top().second.second;
		int cost = inputData.top().first;
		inputData.pop();
		if (!isSameParent(from, to)) {
			uni(to, from);
			ans += cost;
		}
	}
	cout << ans;
}