급하게임개발

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

이 문제는 그냥 최소 스패닝 트리 문제인데 조건이 하나가 더추가가됬다 같은 것 끼리만 연결안하고 연결될때마다 간선의 갯수를 측정해준다음 간선의 갯수가 n-1일 때는 다연결된거니 그냥 값 출력해주면 되고 아니면 -1출력해주면 된다

#include <iostream>
#include <queue>
using namespace std;
int n, m;
char arr[1000];
priority_queue<pair<int,pair<int,int>> , vector<pair<int, pair<int, int>>>,greater<pair<int, pair<int, int>>>> inputData;
int parent[1000];
int findParent(int x) {
	if (parent[x] == x)
		return x;
	else
		return parent[x] = findParent(parent[x]);
}
bool isSameParent(int x, int y) {
	int parentX = findParent(x);
	int parentY = findParent(y);

	if (parentX == parentY)
		return true;
	else
		return false;
}
void uni(int  x, int y) {
	int parentX = findParent(x);
	int parentY = findParent(y);

	parent[parentY] = parentX;
}
int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> arr[i];
		parent[i] = i;
	}
	int u, v, d;
	for (int i = 0; i < m; i++) {
		cin >> u >> v >> d;
		inputData.push({ d,{u,v} });
	}
	int ans = 0;
	int countRoad = 0;
	while (!inputData.empty()) {
		int cost = inputData.top().first;
		int from = inputData.top().second.first;
		int to = inputData.top().second.second;
		inputData.pop();
		if (!isSameParent(from, to) && (arr[from]!=arr[to])) {
			uni(to, from);
			ans += cost;
			countRoad += 1;
		}
	}
	if (countRoad == n - 1)
		cout << ans;
	else
		cout << -1;
}

이 문제는 유니온 파인드 문제이다 이전 게시글에 크루스칼 알고리즘을 사용하면 쉽게 풀린다

#include <iostream>
#include <queue>
using namespace  std;
int n;
int parent[1000];
priority_queue < pair<long long , pair<int, int >> , vector < pair<long long, pair<int, int>>>, greater<pair<long long, pair<int, int>>> > inputData;

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

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

bool isSameParent(int x, int y) {
	int parentX = findParent(x);
	int parentY = findParent(y);
	if (parentX == parentY)
		return true;
	else
		return false;
}

int main() {
	cin >> n;
	int tmp;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> tmp;
			if (i == j)
				continue;
			inputData.push({ tmp,{i,j} });
		}
	}
	for (int i = 0; i < n; i++) {
		parent[i] = i;
	}
	long long ans = 0;
	while (!inputData.empty()) {
		int from = inputData.top().second.first;
		int to = inputData.top().second.second;
		int cost = inputData.top().first;
		inputData.pop();
		if (!isSameParent(from, to)) {
			uni(to, from);
			ans += cost;
		}
	}
	cout << ans;
}

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

이 문제는 위상 정렬 입니다
근데 일반 위상정렬 하고 다르게 cost 값을 갱신 해주어야 했습니다 어찌 보면 플로이드 워셜하고 비슷 하다고 볼수 있습니다
일단 점입 차수가 0인것부터 큐에 넣고 next들을 갱신해 줍니다 next들은 이전애들이 다 되어야하기 때문에 플로이드 워셜처럼 최단이 아닌 최장을 저장하고 있어야 했습니다

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int t;
int main() {
	cin >> t;
	int n, k;
	for (int i = 0; i < t; i++) {
		cin >> n >> k;
		vector<vector<int>> inputData(n+1);
		vector<int> cost;
		vector<int> resultCost;
		int inCount[1001] = { 0, };
		int tmp1, tmp2;
		cost.resize(n + 1);
		resultCost.resize(n + 1);

		for (int i = 1; i<= n; i++) {
			cin >> cost[i];
			resultCost[i]=cost[i];
		}
		for (int i = 0; i < k; i++) {
			cin >> tmp1 >> tmp2;
			inputData[tmp1].push_back(tmp2);
			inCount[tmp2]++;
		}

		queue<int> q;
		for (int i = 1; i <= n; i++) {
			if (inCount[i] == 0) {
				q.push(i);
			}
		}
		while (!q.empty()) {
			int cur = q.front();
			q.pop();
			for (int i = 0; i < inputData[cur].size(); i++) {
				int next = inputData[cur][i];
				inCount[next]--;
				if (resultCost[cur] + cost[next] > resultCost[next]) {
					resultCost[next] = resultCost[cur] + cost[next];
				}
				if (!inCount[next]) {
					q.push(next);
				}
			}
		}
		int w;
		cin >> w;
		cout << resultCost[w] << endl;
	}
}

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

이 문제는 그냥 크루스칼 알고리즘인데 출력이 불친절하다 그냥 00전에 테스트케이스가 여러개 나오는 문제였다

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int parent[200000];
int n, m;
vector<pair<int, pair<int, int>>> inputData;

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

bool isSameParent(int x, int y) {
    return findParent(x) == findParent(y);
}

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

int main() {
    while (true) {
        cin >> n >> m;
        if (n == 0 && m == 0) break; // 종료 조건

        inputData.clear();
        int tmp1, tmp2, tmp3;
        int cost = 0, totalCost = 0;

        for (int i = 0; i < m; i++) {
            cin >> tmp1 >> tmp2 >> tmp3;
            inputData.push_back({ tmp3, {tmp1, tmp2} });
            totalCost += tmp3;
        }

        // 초기화
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }

        sort(inputData.begin(), inputData.end()); // 간선 정렬

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

        cout << totalCost - cost << "\n";
    }

    return 0;
}

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/2252

이 문제는 위상정렬 알고리즘을 사용하는 문제이다
https://terms.naver.com/entry.naver?docId=3579618&cid=59086&categoryId=59093

해당 게시물을 참조하면 이해가 쉬울 것이다
즉 순서에 맞춰서 나열 하면 되는게 위상 정렬 이다

이 문제에서는 어떠한 노드 가 나로 올수 있는 점입차수 라는것을 들고 있어야 한다 점입차수가 0이면 먼저 뽑아도 무방한 노드라고 보면 된다 즉 우리는 이문제를 풀때 점입차수를 비교해가며 큐에 넣어서 pop 하면 되는 문제이다

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

int main() {
	int n, m;
	cin >> n >> m;
	int inCount[100001] = { 0, };
	vector<vector<int>> v(n + 1);
	for (int i = 0; i < m; i++) {
		int tmp1, tmp2;
		cin >> tmp1 >> tmp2;
		v[tmp1].push_back(tmp2);
		inCount[tmp2]++;
	}
	queue<int> q;
	for (int i = 1; i <= n; i++) {
		if (inCount[i] == 0)
			q.push(i);
	}

	while (!q.empty()) {
		cout << q.front() << " ";
		int idx = q.front();
		for (int i = 0; i < v[idx].size(); i++) {
			inCount[v[idx][i]] -= 1;
			if (inCount[v[idx][i]]<=0)
				q.push(v[idx][i]);
		}
		q.pop();
	}
}

일단 전체 코드는 이렇게 된다
입력 받을 때 어떠한 노드를 입력 받고 이노드가 갈수 있는 노드도 Vector에 넣어 놓느다 그후  연결 된 노드의 점입  차수를 1증가 시킨다  이렇게 입력 을 받은 후
우리는 해당 vector를 순회하면 서 일단 점입차수가 0인걸 queue에다가 넣는다
그후 while문으로 큐를 순회하면서 점입차수가 0인 걸 팝해주면 나와 연결된 노드들의 점입 차수를 1감소시켜준다 그렇게 점입차수가 0인 노드들을 지속적으로 queue에 넣었다 팝해주면 해당 문제는 풀린다

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

이 문제는 최소 신장트리 문제이다 이문제의  경우 일부러 프림 알고리즘을 사용해서 풀었다. 프림 알고리즘의 경우 트리들을 계속 이어붙여나가면서 갈수 있는 곳중 최소의 버텍스를 선택해서 계속 트리를 확장해 가는 코드이다. 이전에 게시물에 프림알고리즘에 대해 설명한게 있다. 이문제의 경우는 좌표로 주어지기 때문에 좌표에 인덱스를 부여해주고 거리를 cost로 해서 프림알고리즘을 풀어주면 되는 문제였다

#include <iostream>
#include <queue>
#include <vector>
#include <cmath>

using namespace std;

vector<priority_queue < pair<float, int>, vector<pair<float, int>>, greater<pair<float, int>>>> inputData(101);
int parent[101];
vector<pair<float, float>> stars(101);
float starDistance;
float makeFloat(float x) {
	return round(100 * x) / 100;
}

float getDistance(float x1, float y1, float x2, float y2) {
	return sqrt(pow(x1 - x2, 2) + pow(y1 - y2, 2));
}

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

void uni(int x, int y) {
	x = findParent(x);
	y = findParent(y);

	parent[y] = x;
}

bool isSameParent(int x, int y) {
	x = findParent(x);
	y = findParent(y);

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

}
int main() {
	int n;
	cin >> n;

	for (int i = 1; i <= n; i++) {
		float tmp1, tmp2;
		cin >> tmp1 >> tmp2;
		stars[i] = { tmp1,tmp2 };
	}

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			float distance = getDistance(stars[i].first, stars[i].second, stars[j].first, stars[j].second);
			if (i == j)
				continue;
			inputData[i].push({ distance, j });

			
		}
		parent[i] = i;
	}

	for (int i = 1; i <= n; i++) {
		int star1 = 1;
		while (!inputData[1].empty()) {
			int star2 = inputData[1].top().second;
			float cost = inputData[1].top().first;
			inputData[1].pop();

			if (!isSameParent(star1, star2)) {
				starDistance += cost;
				uni(star1, star2);
				while (!inputData[star2].empty()) {
					inputData[1].push({ inputData[star2].top().first, inputData[star2].top().second });
					inputData[star2].pop();
				}
				break;
			}
		}
	}

	cout << round(starDistance*100);
}

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