급하게임개발

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/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에 넣었다 팝해주면 해당 문제는 풀린다