본문 바로가기
알고리즘/알고리즘 문제풀이

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

by E145 2021. 7. 5.
반응형

백준 1922 네트워크 연결

 

 

1922번: 네트워크 연결

이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다.

www.acmicpc.net

 

문제 설명

 

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

 

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

 

 - 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) 알고리즘

프림(Prim) 알고리즘 프림 알고리즘이란?  - 최소 비용 신장 트리(MST)를 찾는 알고리즘  - 시작 정점에서 출발하여 신장 트리를 확장하는 알고리즘  - 시간 복잡도 : 인접 행렬 사용 시 O($V^2$)  우

9327144.tistory.com

 

 - 노드가 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;
}

 

 

 

 

 

 

 

 

 

반응형

'알고리즘 > 알고리즘 문제풀이' 카테고리의 다른 글

[BOJ-1939] 중량제한 (C++)  (0) 2021.07.07
[BOJ-1937] 욕심쟁이 판다 (C++)  (0) 2021.07.06
[BOJ-1613] 역사(C++)  (1) 2021.07.05
[BOJ-1162] 도로포장(C++)  (0) 2021.07.04
[BOJ-1062] 가르침(C++)  (0) 2021.07.03

댓글