[백준 4650] Jungle Roads (C++)

문제 링크: https://www.acmicpc.net/problem/4650

4650번: Jungle Roads

1. 주의할 점

- 매 TC마다 Par[] 배열 초기화

- MST 알고리즘에 대해 알고 있어야 한다

 

2. 구현

- 크루스칼 알고리즘을 통해 MST 문제를 해결한다

- Find_parent(x) 함수를 통해 x의 부모를 반환한다

- Make_union(a,b) 함수를 통해 a와 b의 부모가 일치하지 않는다면 합친다

- 입력받는 모든 간선에 대한 정보를 우선순위 큐에 저장하며, 간선의 가중치를 오름차순으로 정렬한다

- While문을 통해 우선순위 큐에서 1개의 원소를 빼면서 부모가 일치하지 않으면 합치며 Cnt++한다. Cnt가 Num-1와 같다면 MST가 완성되었으므로 종료한다

 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
struct info {
	int start, end, val;
};
struct cmp {
	bool operator()(info &a, info &b) {
		return a.val > b.val;
	}
};
info tmp;
int num, val, edge;
int par[30];
int find_parent(int x) {
	if (par[x] == x) return x;
	return par[x] = find_parent(par[x]);
}

void make_union(int a, int b) {
	a = find_parent(a);
	b = find_parent(b);
	if (a > b) par[a] = b;
	else if (a < b) par[b] = a;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	char c;
	while (1) {
		cin >> num;
		if (num == 0) break;
		priority_queue<info, vector<info>, cmp> pq;
		long long result = 0;
		for (int i = 1; i <= num; i++)
			par[i] = i;
		for (int i = 1; i < num; i++) {
			cin >> c >> edge;
			for (int j = 0; j < edge; j++) {
				cin >> c >> val;
				tmp.start = i;
				tmp.end = c - 'A' + 1;
				tmp.val = val;
				pq.push(tmp);
			}
		}
		int cnt = 0;
		while (!pq.empty()) {
			int cs = pq.top().start;
			int ce = pq.top().end;
			int cv = pq.top().val;
			pq.pop();
			int ps = find_parent(cs);
			int pe = find_parent(ce);
			if (ps == pe) continue;
			make_union(cs, ce);
			cnt++;
			result += cv;
			if (cnt == num - 1)
				break;
		}
		cout << result << '\n';
	}
	system("pause");
	return 0;
}