급하게임개발

https://www.acmicpc.net/problem/1922

이번 문제도 그래프를 이용해 최소 신장 트리를 만드는 문제이다 단 저번 게시물에는 크루스칼 알고리즘을 이용 하였으나 이번 알고리즘은 프림 알고리즘을 이용해서 풀었다.

프림 알고리즘은 현재 나와 연결된 노드들을 점점확장하면서 최소 신장 트리를 만드는 것이다
프림 알고리즘은 크루스칼알고리즘과 다르게 간선들이 많을 때 효율적이다.

프림알고리즘의 로직은 대충 일단 내가 갈수 있는 곳중 가까운 곳을 연결한다. 그리고 내가 갈수 있는 곳과 그 갈수 있는 버텍스를 통해서 갈수 있는 곳중 가장 비용이 낮은 곳으로 간다

위의 과정을 vertex의 갯수-1 만큼 반복해주면 된다.

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
int parent[1001];
vector<priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>> inputData(1001);
int findParent(int x) {
	if (parent[x] == x)
		return x;
	else return parent[x] = findParent(parent[x]);
}
bool isSameParent(int x, int y) {
	int parentOfX = findParent(x);
	int parentOfY = findParent(y);
	if (parentOfX == parentOfY) {
		return true;
	}
	else {
		return false;
	}
}

void uni(int x, int y) {
	x = findParent(x);
	y = findParent(y);
	parent[y] = x;
}
int main() {
	int n, m;
	cin >> n;
	cin >> m;
	int com1 = 0, com2 = 0, cost = 0,result=0;
	for (int i = 0; i < m; i++) {
		int from, to, cost;
		cin >> from >> to >> cost;
		inputData[from].push({ cost,to });
		inputData[to].push({ cost,from });
	}
	for (int i = 1; i <= n; i++) {
		parent[i] = i;
	}
	for (int i = 1; i < n ; i++) {
		while (!inputData[1].empty()) {
			com1 = 1;
			com2 = inputData[1].top().second;
			cost = inputData[1].top().first;
			inputData[1].pop();
			if (!isSameParent(com1, com2)) {
				result += cost;
				uni(com1, com2);
				while (!inputData[com2].empty()) {
					inputData[com1].push(inputData[com2].top());
					inputData[com2].pop();
				}
				break;
			}
		}
	}
	cout << result;
}

https://www.acmicpc.net/problem/1197

이 문제의 경우 최소 신장트리를 만들어 내는 문제이다 모든 정점들을 이었을 때 각 간선들의 최소가 되는 트리를 최소 신장트리라고 한다  이문제의 경우 내가 트리의 크루스칼 알고리즘을 이용해서 풀었다

크루스칼 알고리즘은 
1. 각 경로들의 cost 값으로 오름차순 정렬 한다
2. 각 경로들의 vertex 간 비교해서 각 vertex들이 이어진 경로의 root와 비교해서 서로 다르면 잇고 아니면 연결하지 않는다
3. 2의 과정을 반복한 후 Cost의 값을  도출한다

#include<iostream>
#include <vector>
#include <algorithm>
using namespace std;
// 가중치 start end순
vector<pair<int, pair<int, int>>> inputData;
int parent[10001] = { 0, };

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

bool sameParent(int x, int y) {
	x = findParent(x);
	y = findParent(y);
	if (x == y)
		return true;
	else
		return false;
}
void uni(int  x, int y) {
	x = findParent(x);
	y = findParent(y);
	parent[y] = x;
}
int main() {
	int  v, e,cost;
	cost = 0;
	cin >> v >> e;
	int tmp1, tmp2, tmp3;
	for (int i = 0; i < e; i++) {
		cin >> tmp1 >> tmp2 >> tmp3;
		inputData.push_back({ tmp3,{tmp1,tmp2} });
	}

	sort(inputData.begin(), inputData.end());
	for (int i = 1; i <= v; i++) {
		parent[i] = i;
	}

	for (int i = 0; i<inputData.size(); i++) {
		if (!sameParent(inputData[i].second.first, inputData[i].second.second)) {
			uni(inputData[i].second.first, inputData[i].second.second);
			cost += inputData[i].first;
		}
	}
	cout << cost;
}