[C++] 백준 1197번 최소 스패닝 트리

www.acmicpc.net/problem/1197

1197번: 최소 스패닝 트리

문제를 보고 크루스칼 알고리즘이나 프림알고리즘으로 풀어야 겠다는 생각을 했는데

둘 다 실제로 구현해본적이 없어서 고민을 하다가

결국 답을 보고 풀 수 있었다..

 

#define _CRT_SECRUE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
using namespace std;

int v, e, c;
long long sum;
int visit[10001];
vector<vector<pair<int, int>>> edge;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;

void prim(int v) {
	visit[v] = 1;		//방문 노드 체크
	for (auto u : edge[v]) {
		if (!visit[u.second]) {		//방문 노드에 연결된 모든 간선 추가
			pq.push({ u.first, u.second });
		}
	}

	while (!pq.empty()) {		//방문 노드와 연결된 간선 중 최소값 더하기
		auto w = pq.top();
		pq.pop();
		if (!visit[w.second]) {
			sum += w.first;
			prim(w.second);
			return;
		}
	}
}

int main() {
	int x, y, z;
	cin >> v >> e;
	edge.resize(v + 1);
	for (int i = 0; i < e; i++) {
		cin >> x >> y >> z;
		edge[x].push_back({ z,y });
		edge[y].push_back({ z,x });
	}
	prim(1);
	cout << sum;
	return 0;
}

 

출처: dhpark-ghost.herokuapp.com/2018/06/12/c-peurim-prim-algorijeum/