급하게임개발

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

이 문제의 경우 일반 크루스칼을 이용하여 모든 행성간의 거리를 계산해서 하려고 하다보니 메모리 초과가 발생하였다.
이 문제의 경우 해결방식은 행성의 x,y,z 좌표를 추출한 후 각각의 Vector에 저장한뒤  해당 Vector를 정렬해준 후 차이를 계산하여 그 값을 바탕으로 크루스칼 알고리즘을 돌리는 것이었다

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdlib>
using namespace std;
vector<pair<int, pair<int, int>>> inputData;
int parent[100001];
vector<pair<int, int>> v[3];
int n;
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() {
	cin >> n;
	int tmp1, tmp2, tmp3;
	for (int i = 0; i < n; i++) {
		cin >> tmp1 >> tmp2 >> tmp3;
		v[0].push_back({ tmp1,i });
		v[1].push_back({ tmp2,i });
		v[2].push_back({ tmp3,i });
	}
	sort(v[0].begin(), v[0].end());
	sort(v[1].begin(), v[1].end());
	sort(v[2].begin(), v[2].end());
	int cost = 0;
	for (int i = 0; i < n - 1; i++)
	{
		inputData.push_back(make_pair(abs(v[0][i].first - v[0][i + 1].first), make_pair(v[0][i].second, v[0][i + 1].second)));
		inputData.push_back(make_pair(abs(v[1][i].first - v[1][i + 1].first), make_pair(v[1][i].second, v[1][i + 1].second)));
		inputData.push_back(make_pair(abs(v[2][i].first - v[2][i + 1].first), make_pair(v[2][i].second, v[2][i + 1].second)));
	}
	sort(inputData.begin(), inputData.end());
	for (int i = 0; i < n; 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;
}

전체 코드는 이렇게 된다 일단 크루스칼의 기본 함수는 알것이라 생각하고 설명을 생략한다

	for (int i = 0; i < n; i++) {
		cin >> tmp1 >> tmp2 >> tmp3;
		v[0].push_back({ tmp1,i });
		v[1].push_back({ tmp2,i });
		v[2].push_back({ tmp3,i });
	}

자 이코드는 사용이유가 우리는 어차피 x간의 차와 y간의 차가 z간의 차가 가장 작은것을 이용해서 문제를 해결할것이므로 이렇게 각각 분리해서 인풋받는다 i는 vertex의 번호다
 그후 정렬을 해주는데 정렬을 하면 각좌표별로 크기별로 정렬이 될것이므로 무조건 나의 다음 vertex와의 거리가 연결 cost가 될거이다 다음다음꺼는 봐줄필요가 없는게 어차피 x값기준으로 만 연산을 할건데 멀리 있으면 연산 할필요가 없기 때문이다

이이후는 일반 크루스칼과 같다

	for (int i = 0; i < n - 1; i++)
	{
		inputData.push_back(make_pair(abs(v[0][i].first - v[0][i + 1].first), make_pair(v[0][i].second, v[0][i + 1].second)));
		inputData.push_back(make_pair(abs(v[1][i].first - v[1][i + 1].first), make_pair(v[1][i].second, v[1][i + 1].second)));
		inputData.push_back(make_pair(abs(v[2][i].first - v[2][i + 1].first), make_pair(v[2][i].second, v[2][i + 1].second)));
	}

이런식으로 vertex간 x거리 y거리  z거리를 넣는데 나의 다음거와의 거리만 넣어서 최솟값만 넣는다 중복이 나중에 발생해도 우리는 이 inputData를 정렬할거기 때문에 무조건 짧은 거와 연결된다

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

이 문제의 경우  최소 신장  트리 문제중 하나로 일단  최소 신장 트리를 만드는 알고리즘으로 크루스칼을 사용해서 풀었다
크루스칼 알고리즘 전전 게시물에 작성했다시피 경로의 Cost가 낮은 경로들 부터 연결을 하지만 서로의 root 가 다른 경로들 만 연결 하고 각자의 root들을 합쳐질때마다 업데이트 해주면 되는 문제 였다 

이 문제에서는 핵심적으로 4개의로직이 있다.

1. 부모를 찾는 로직

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

이 로직은 x의 부모 root를찾는 코드로 재귀적으로 부모를 찾으면서 부모를 업데이트도 해주는 코드이다

2. 같은 부모인지 찾는 로직

bool sameParent(int x, int y) {
	x = findParent(x);
	y = findParent(y);
	if (x == y)
		return true;
	else
		return false;

3. 2개의 다른 트리를 합치는 로직 합칠때는 합쳐진 트리의 부모만 바꿔주면 된다

void uni(int  x, int y) {
	x = findParent(x);
	y = findParent(y);
	parent[y] = x;
}

4. cost가 낮은 순 부터 오름차순으로 입력 데이터를 정렬 한다 그후 루프를 돌면서  2번 3번 과정을 반복해준다 그후 연결된 cost중 가장  높은부분을 뺴준다 그 이유는 이문제에서 마을을 두개로 분리한다고 하였으니 가장 비용이 많이 드는 길 을 없애면 된다

	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;
			cnt += 1;
			if (cnt == v - 1) {
				cost -= inputData[i].first;
			}
		}
	}

전체 코드는 아래와 같다

#include<iostream>
#include <vector>
#include <algorithm>
using namespace std;
// 가중치 start end순
vector<pair<int, pair<int, int>>> inputData;
int parent[100001] = { 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;
	long long cost;
	cost = 0;
	int cnt = 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;
			cnt += 1;
			if (cnt == v - 1) {
				cost -= inputData[i].first;
			}
		}
	}
	cout << cost;
}

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