[알고리즘] c++ cpp 네트워크 연결

포인트

1. mst 를 잘 이해할 수 있는가를 묻는 문제

(mst 는 크루스칼 알고리즘, 프림 알고리즘 등이 있다. ) 크루스칼 알고리즘이 빠르긴하다. 

🧶문서는 항상 수정 될 수 있습니다. 비판은 환영합니다. 

프림 알고리즘

#include <iostream>
#include <queue>
#include <vector>
#include <tuple>

using namespace std;

int n, m;
bool visited[1001];
vector<pair<int, int>> map[1001]; //가중치, 목적지
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq; //가중치기준 최소힙

int prim() {
	int ans = 0;
	pq.push({0, 1});
	while (!pq.empty()) {
		int cost, x;
		tie(cost, x) = pq.top();
		pq.pop();
		if (visited[x]) continue; //방문했으면 거른다.
		visited[x] = true;
		ans += cost;
		for (auto next : map[x]) {
			if (!visited[next.second]) {
				pq.push(next);
			}
		}
	}
	return ans;
}

int main() {

	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		map[a].push_back({c, b});
		map[b].push_back({c, a});
	}
	int result = prim();
	cout << result << endl;

	return 0;
}

유니온 파인드

#include<iostream>
#include<vector>
#include<algorithm>
#include <tuple>

#define endl "\n"
#define MAX 100000 + 1
using namespace std;

int n, m, answer;
int parent[MAX];

vector<tuple<int, int, int>> map;


int find(int x) {
	if (parent[x] == x) return x;
	else return parent[x] = find(parent[x]);
}

void Union(int x, int y) {
	x = find(x);
	y = find(y);

	if (x != y) parent[y] = x;
}

bool same_parent(int x, int y) {
	x = find(x);
	y = find(y);

	if (x == y) return true;
	else return false;
}


int main() {
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		
		map.push_back ({ c, a, b });
	}
	sort(map.begin(), map.end()); //정렬
	
	for (int i = 1; i <= n; i++) {
		parent[i] = i; // 초기값 설정
	}

	for (int i = 0; i < m; i++) {
		int cost, x, y;
		tie (cost, x, y)=map[i];
		if (same_parent(x, y) == false) {
			Union(x, y);
			answer = answer + cost;
		}
	}

	cout << answer << endl;

	return 0;
}