[BOJ1922] 네트워크 연결

[BOJ1922] 네트워크 연결

문제 링크

문제 설명

• 컴퓨터들이 허브가 없어 1:1로 연결되어 있다.
• 모든 컴퓨터들은 연결되어 있다.
• a컴퓨터와 b컴퓨터가 연결되어 있을 때, 에지의 가중치가 주어진다.
• 모든 컴퓨터들을 연결하는데 필요한 최소 비용 출력하는 문제

코드 리뷰

• 시작 지점이나 목표 지점이 없이 단순히 모든 컴퓨터들을 연결하데 필요한 최소 비용 문제이므로 바로 MST를 떠올려야 한다.
• MST를 만드는 알고리즘 중 이 문제는 프림 알고리즘을 통하여 해결하였다.
• 즉 모든 에지의 가중치를 정렬해놓고 시작하지 않고, 하나의 정점에서 인접한 정점의 에지 가중치 중 가장 낮은 가중치를 선택하고 그를 통해 선택된 새로운 정점까지 확장하여, 인접한 에지 가중치 중 최소 가중치를 선택하는 식으로 진행한다. 이 때 사이클이 생기는 에지는 선택하지 않는다.

#include <iostream>
#include <queue>
#include <vector>
#include <utility>
#include <functional>
#include <algorithm>
using namespace std;

vector <pair<int,int>> v[1001];
priority_queue <pair<int,int>, vector <pair<int,int>>, greater<pair<int,int>>> pq;
int N, M;
bool visit[1001];

int prim(int start) {
	int ans = 0;
	int edge_max = N - 1;
	int edge_cnt = 0;
	for (int i = 0; i < v[start].size(); i++) {
		pq.push(make_pair(v[start][i].second, v[start][i].first));
	}
	visit[start] = true;
	while (!pq.empty() && edge_cnt <= edge_max) {
		if (visit[pq.top().second]) {
			pq.pop();
			continue;
		}
		int now = pq.top().second;
		ans += pq.top().first;
		edge_cnt++;
		pq.pop();
		visit[now] = true;
		for (int i = 0; i < v[now].size(); i++) {
			if (visit[v[now][i].first]) continue;
			else pq.push(make_pair(v[now][i].second, v[now][i].first));
		}
	}
	return ans;
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> N;
	cin >> M;
	for (int m = 1; m <= M; m++) {
		int a, b, w;
		cin >> a >> b >> w;
		v[a].push_back(make_pair(b, w));
		v[b].push_back(make_pair(a, w));
	}
	cout << prim(1) << '\n';
	return 0;
}