[BOJ] 16398번 행성 연결 (C++)

링크 (https://www.acmicpc.net/problem/16398)

16398번: 행성 연결

무난한 최소 스패닝 트리 문제이다. MST 문제를 항상 크루스칼 알고리즘으로만 풀었는데 이번엔 프림 알고리즘으로 풀어봤다!

정답이 int 범위보다 클 수 있으므로 long long으로 해주어야 한다.

---

[소스코드]

	/*
	BOJ 16398번: 행성 연결
	DATE: 2022-03-02
	Prim Algorithm
	*/
	#include <iostream>
	#include <vector>
	#include <queue>
	#define MAX 1001
	#define pii pair<int,int>
	using namespace std;
	vector<pii> edge[MAX];
	bool visited[MAX];
	long long prim(){
	long long ans = 0;
	priority_queue<pii, vector<pii>, greater<pii>> pq;
	pq.push({0, 1});
	while(!pq.empty()){
	int dis = pq.top().first;
	int cur = pq.top().second;
	pq.pop();
	if(visited[cur]) continue;
	visited[cur] = true;
	ans += dis;
	for(int i = 0 ; i < edge[cur].size() ; i++){
	if(!visited[edge[cur][i].second]) pq.push(edge[cur][i]);
	}
	}
	return ans;
	}
	int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int n, num;
	cin >> n;
	for(int i = 1 ; i <= n ; i++){
	for(int j = 1 ; j <= n ; j++){
	cin >> num;
	if(i == j) continue;
	edge[i].push_back({num, j});
	}
	}
	cout << prim();
	return 0;
	}

view raw 16398.cpp hosted with ❤ by GitHub

---

2022-03-02

Gold 4

- 그래프 이론

- 최소 스패닝 트리