[BOJ-1922] 네트워크 연결(C++)

백준 1922 네트워크 연결

 

1922번: 네트워크 연결

 

문제 설명

 

 - 도현이는 컴퓨터를 모두 연결하는 네트워크를 구축하려 한다.

 

 - 컴퓨터와 컴퓨터는 모두 직접 연결하여야 한다.

 

 - a와 b가 연결되어 있고, b와 c가 연결되어 있다면 a와 c도 연결되어 있는 것이다.

 

 - 모든 컴퓨터를 연결하는데 비용의 최소값을 출력하라.

---

 

입력 값

 

 - 첫째 줄에 컴퓨터의 수 N( 1<= N <= 1000) 가 주어진다.

 

 - 둘째 줄에 연결할 수 있는 선의 수 M( 1<= M <= 100,000) 가 주어진다.

 

 - 셋째 줄에 M+2 번째 줄까지 총 M개의 줄에 각 컴퓨터를 연결하는데 드는 비용이 주어진다.

   이 비용 정보는 세 개의 정수로 주어진다. 만약 a, b, c가 주어지면

   a 와 b를 연결하는데 c의 비용이 든다는 것이다. ( 1<= c <= 10,000, a와 b는 같을 수 있다.)

 

---

 

 

예제

 

---

 

 

문제 분석

 

 - 이 문제는 그래프에서 MST(최소 비용 신장 트리)를 찾는 문제이다.

 

 - 프림 알고리즘을 사용하여 간단하게 해결할 수 있다.

최소 비용 신장 트리 - 프림(Prim) 알고리즘

 

 - 노드가 N개, 간선이 M개 있기 때문에 시간복잡도는 O(MlogN)이 된다.

   즉, O(100,000 x log(1000)) = 약 100만이 된다.

 

 

---

 

 

소스 코드

 

#include <bits/stdc++.h>

using namespace std;

vector<pair<int,int>> v[1001];

bool visited[1001];

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N, M;

	int result = 0;

	cin >> N >> M;
	
	for (int i = 0; i < M; i++) {
		int a, b,c;
		cin >> a >> b >> c;
		v[a].push_back({ b,c });
		v[b].push_back({ a,c });
	}

	// cost, index
	priority_queue<pair<int, int>> pq;
	pq.push({ 0,1 });

	while (!pq.empty()) {

		int nowCost = -pq.top().first;
		int nowIndex = pq.top().second;

		pq.pop();

		if (visited[nowIndex]) {
			continue;
		}
		visited[nowIndex] = true;
		result += nowCost;

		for (auto next : v[nowIndex]) {
			int nextIndex = next.first;
			int nextCost = next.second;

			if (visited[nextIndex]) {
				continue;
			}
			pq.push({ -nextCost,nextIndex });
		}



	}

	cout << result << endl;



	return 0;
}