백준 1922번 네트워크 연결

< 백준 1922번 네트워크 연결 - 마포 코딩박 >

사용한 알고리즘: MST


두 개의 컴퓨터를 연결하는데 비용이 들 때 모든 컴퓨터를 연결하는데 필요한 최소 비용을 구하는 문제였습니다. MST의 대표적인 문제였습니다.
 (보통 MST 구현에 struct로 저장하고 이를 pq로 돌리지만, 연결 비용의 최대값이 10^4으로 작게 주어져 배열을 사용했습니다.)

문제풀이는 다음과 같습니다.

(1) (코드 13~23)
 MST 구현을 하려면 Union-Find 가 필요합니다.
 두 컴퓨터 a, b가 연결되었는지(같은그룹인지) 판단하고 연결을 해주는 역할을 합니다.

(2) (코드 10~13, 35~50)
 'cost[x] : x 비용으로 연결가능한 컴퓨터 a, b 저장' 이라고 설정하고 비용을 작은것부터 (1->10^4) 순서대로 돌아보며 Union-Find 를 써서 연결해야하는지 여부를 판단했습니다.
 N 개의 컴퓨터를 한 그룹으로 연결하려면 N-1번의 연결이 필요합니다.

	#include <iostream>
	#include <vector>
	#include <utility>
	using namespace std;
	#define pii pair<int, int>
	int N, M;
	int root[1001];
	int ans;
	// 사실 struct 써서 pq 돌려야 하지만... cost 값이 작길래....
	vector<pii> cost[10001];
	// 컴퓨터가 모두 연결되었는지 판단.
	bool flag;
	int F(int a){
	if(root[a]<0) return a;
	return root[a] = F(root[a]);
	}
	void U(int a, int b){
	int A = F(a);
	int B = F(b);
	if(A==B) return;
	root[B] += root[A];
	root[A] = B;
	}
	int main(){ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
	cin >> N >> M;
	for (int i = 1; i <= N; ++i) root[i] = -1;
	for (int i = 0; i < M; ++i){
	int a, b, c;
	cin >> a >> b >> c;
	cost[c].push_back(pii(a,b));
	}
	for (int i = 0; i < 10001; ++i){
	if(flag) break;
	if(cost[i].empty())
	continue;
	for(int j=0; j<cost[i].size();++j){
	if(flag) break;
	int a = cost[i][j].first;
	int b = cost[i][j].second;
	if(F(a)==F(b)) continue;
	U(a,b);
	ans += i;
	if(root[b]==-N)
	flag = true;
	}
	}
	cout << ans << '\n';
	return 0;
	}

view raw BOJ 1922.cpp hosted with ❤ by GitHub