728x90
반응형
1922번: 네트워크 연결
문제
https://www.acmicpc.net/problem/1922
풀이
기본적인 최소 신장 트리(Minimun Spanning Tree, MST)를 사용하는 문제다. 프림 알고리즘으로 구현하는 MST 알고리즘을 사용했다. MST 알고리즘은 아래 글을 보고 공부했다. 아직 유니온 파인드를 모르기 때문에 크루스칼 알고리즘은 보류해놨다.
https://4legs-study.tistory.com/112
코드
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
int N, M;
vector<pii> graph[10001];
int prim() {
priority_queue<pii> pq;
vector<int> visited(N + 1, 0);
visited[1] = 1;
for (pii edge : graph[1])
pq.push(edge);
int cost = 0;
while (!pq.empty()) {
int weight = -pq.top().first;
int node = pq.top().second;
pq.pop();
if (!visited[node]) {
visited[node] = 1;
cost += weight;
for (pii next : graph[node])
if (!visited[next.second])
pq.push(next);
}
}
return cost;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cin >> N >> M;
while (M--) {
int a, b, c;
cin >> a >> b >> c;
graph[a].push_back({-c, b});
graph[b].push_back({-c, a});
}
cout << prim();
return 0;
}
728x90
반응형
'Problem Solving > BOJ' 카테고리의 다른 글
[백준 / BOJ] C++ 15926 현욱은 괄호왕이야!! (0) | 2023.03.24 |
---|---|
[백준 / BOJ] C++ 16398 행성 연결 (0) | 2023.03.24 |
[백준 / BOJ] C++ 16940 BFS 스페셜 (0) | 2023.03.24 |
[백준 / BOJ] C++ 10423 전기가 부족해 (0) | 2023.03.23 |
[백준 / BOJ] C++ 4386 별자리 만들기 (0) | 2023.03.23 |