문제링크
https://www.acmicpc.net/problem/16398
풀이방법
해당 문제는 최소 신장 트리를 구하는 알고리즘을 사용하여 해결할 수 있다. 최소 신장 트리를 찾는 알고리즘에는 두 가지가 있다. 하나는 크루스칼 알고리즘 나머지 하나는 프림 알고리즘이다. 이 중 프림 알고리즘을 사용하여 해당 문제를 해결하였다. 최소 신장 트리를 찾는 알고리즘에 대한 개념이 없다면 아래 영상을 참고하자.
코드
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
int n;
vector<pair<int, int>> adj[1005];
// (비용, 정점 번호)
bool chk[1005];
// chk[i] : i번째 정점이 최소 신장 트리에 속해있는가?
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
int cost;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
cin >> cost;
if (i == j) continue;
adj[i].push_back({ cost,j });
}
}
// tuple<int,int,int> : {비용, 정점 1, 정점 2}
priority_queue < tuple<int, int, int>, vector < tuple<int, int, int>>, greater<tuple<int, int, int>> > pq;
chk[1] = 1;
for (auto nxt : adj[1])
{
pq.push({ nxt.X,1,nxt.Y });
}
int cnt = 0;
int ans = 0;
while (cnt < n-1)
{
int cost, a, b;
tie(cost, a, b) = pq.top(); pq.pop();
if (chk[b]) continue;
ans += cost;
chk[b] = 1;
cnt++;
for (auto nxt : adj[b]) {
if (chk[nxt.Y]) continue;
pq.push({ nxt.X,b,nxt.Y });
}
}
cout << ans << '\n';
return 0;
}
'CS(Computer Science)지식 > [C++][코딩 테스트] 자료구조 및 알고리즘' 카테고리의 다른 글
백준 11404번: 플로이드 (C++) (0) | 2024.02.03 |
---|---|
백준 1647번: 도시 분할 계획 (C++) (0) | 2024.02.03 |
백준 9372번: 상근이의 여행 (C++) (0) | 2024.02.03 |
백준 1368번: 물대기 (C++) (0) | 2024.02.03 |
백준 1197번: 최소 스패닝 트리 (C++) (0) | 2024.02.02 |