급하게임개발

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;
}