[C++] 백준 1922번 - 네트워크 연결

문제를 읽어보면 Minimum Spanning Tree를 구하는 것이라는 것을 파악할 수 있다.

MST라고 판단할 수 있는 조건은 다음과 같다

• Complete Graph
• 간선에 weight가 있어야함

 문제해결기법 수업 중의 일화인데, DFS 문제를 발표하는 순서가 와서 처음 문제를 풀 때의 사고과정을 설명하던 중 처음 문제 접근을 Prim Algorithm으로 접근해서 풀다가 Prim Algorithm으로 접근했을 때의 output이 문제의 예시 output과 달라 MST를 구하지 않고 DFS로 풀었습니다 라고 발표를 했었다. 

 그러자 교수님께서 사고의 흐름을 칭찬하셨지만 문제의 조건으로 그래프를 먼저 그려봤다면 MST의 조건에 의해서 Prim은 생각조차 하지 않아도 된다고 하셔서 머쓱했던 적이 있다. 

 여튼 여담이었고, 단순하게 Prim Algorithm을 통해 MST를 만들고 MST의 가중치의 최소값을 출력하면 된다.

 

#include <bits/stdc++.h>
#define endl '\n'
#define pii pair<int, int>
using namespace std;

int n, m;
vector<pii> graph[1001];
bool visited[1001];

void prim() {
	priority_queue<pii, vector<pii>, greater<>> pq;
	int result = 0;
	pq.push({ 0, 1 });
	for (int i = 1; i <= n; i++) {
		while (!pq.empty() && visited[pq.top().second]) pq.pop();
		int next = pq.top().second;
		int min_cost = pq.top().first;
		visited[next] = true;
		result += min_cost;
		for (auto k : graph[next]) {
			pq.push({ k.second, k.first });
		}
	}
	cout << result << endl;
}

int main() {

	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	cin >> n;
	cin >> m;
	while (m--) {
		int x, y, w; cin >> x >> y >> w;
		graph[x].push_back({ y, w });
		graph[y].push_back({ x, w });
	}

	prim();

	return 0;
}