반응형
백준 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(최소 비용 신장 트리)를 찾는 문제이다.
- 프림 알고리즘을 사용하여 간단하게 해결할 수 있다.
- 노드가 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 |
댓글