[백준 1922] 네트워크 연결 (C++)

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

1922번: 네트워크 연결

1. 주의할 점

- MST 알고리즘에 대해 알고 있어야 한다(필자는 크루스칼 알고리즘을 통해 풀 예정이다)

 

2. 구현

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

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

- Make_union(int a, int b) 함수를 통해 A와 B의 부모가 일치하지 않는다면, 부모의 수가 작은쪽으로 합친다

- 입력받은 간선의 정보를 모두 우선순위큐에 넣고 간선의 크기가 작은것부터 뽑아서 사용한다

- Cycle이 생성되지 않도록 간선의 시작점과 끝점이 이미 같은 부모라면 Continue를 통해 무시한다

 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
struct info {
	int s, e, val;
};
struct cmp {
	bool operator()(info &a, info &b) {
		return a.val > b.val;
	}
};
info tmp;
int node, edge, s, e, val;
int par[1001];
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[b] = a;
	else if (a > b) par[a] = b;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> node >> edge;
	priority_queue<info, vector<info>, cmp> pq;
	for (int i = 1; i <= node; i++)
		par[i] = i;
	for (int i = 0; i < edge; i++) {
		cin >> s >> e >> val;
		tmp.s = s;
		tmp.e = e;
		tmp.val = val;
		pq.push(tmp);
	}
	long long result = 0;
	while (!pq.empty()) {
		int cs = pq.top().s;
		int ce = pq.top().e;
		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);
		result += cv;
	}
	cout << result;
	system("pause");
	return 0;
}