[C/C++] 백준 - 1414번 : 불우이웃돕기

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

1414번: 불우이웃돕기

1. 알파벳 아스키코드 값 계산을 통해 가지고 있는 총 합 구하기

2. 크루스칼 / 프림 알고리즘으로 모든 노드를 연결 시키는 최소의 비용 구하기

3. ①번에서 구한 총 합에서 ②번에서 구한 비용 빼면 정답

#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <set>
#include <map> 
#define fastio ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define ENDL cout << endl
#define ll long long	
#define ull unsigned long long
#define INF 987654321
#define Mod 1000000
#define endl '\n'
#define pil pair<int,int>

using namespace std;

int N, sum;
int parent[105];
priority_queue<pair<int, pair<int, int>>> pq;

void init() {
	for (int i = 1; i <= N; i++) {
		parent[i] = i;
	}
}

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

bool isSame(int p, int q) {
	p = getParent(p);
	q = getParent(q);

	if (p == q) return true;
	return false;
}

void nodeUnion(int p, int q) {
	p = getParent(p);
	q = getParent(q);

	if (p < q) parent[q] = p;
	else parent[p] = q;
}

void input() {
	cin >> N;
	
	char c;
	int cost = 0;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			cin >> c;
			if ('a' <= c && c <= 'z') {
				cost = c - 'a' + 1;
				sum += cost;
				pq.push({ -cost, {i, j} });
			}
			else if ('A' <= c && c <= 'Z') {
				cost = c - 'A' + 27;
				sum += cost;
				pq.push({ -cost, {i, j} });
			}
		}
	}
}

int solution() {
	init();
	int edge = 0;
	while (!pq.empty()) {
		pair<int, pair<int, int>> cur = pq.top();
		pq.pop();

		if (isSame(cur.second.first, cur.second.second)) continue;

		nodeUnion(cur.second.first, cur.second.second);
		sum -= (cur.first * -1);
		edge += 1;
	}
	// cout << "->" << sum << endl;
	return edge == N - 1 ? sum : -1;
}

int main() {
	fastio;
	input();
	cout << solution() << endl;

	return 0;
}