ACM Craft (feat. 백준, 1005번)

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

1005번: ACM Craft

반응형

// woohyeon.kim
// https://www.acmicpc.net/problem/1005
#include <iostream>
#include <map>
#include <vector>
#include <queue>
using namespace std;
int main() {
	ios::sync_with_stdio(false), cin.tie(), cout.tie();
	register int T, N, K, arr[1001], dp[1001], check[1001];
	register map<int, vector<int>> route;
	register queue<int> q;
	register vector<pair<int, int>> order;
	cin >> T;
	for (register int t = 0, ans; t < T; ++t) {
		route.clear(), order.clear();

		cin >> N >> K;
		for (register int i = 1; i <= N; ++i)
			cin >> arr[i], dp[i] = arr[i], check[i] = 0;
		for (register int k = 0, x1, x2; k < K; ++k)
			cin >> x1 >> x2, route[x1].push_back(x2), ++check[x2];
		
		// 간선중 2번 이상인 아이들이 있을 수 있으므로, 정리해줌
		// 가령 1->2, 2->3, 1->3 이 있다면 1->2, 1->3, 2->3 순서로 풀어줌 (즉, 2->3이 1->3 이후 계산될 수 있도록)
		for (register int n = 1; n <= N; ++n)
			if (!check[n])
				q.push(n);

		while (!q.empty()) {
			register int x1 = q.front(); q.pop();
			for (register int i = 0; i < route[x1].size(); ++i)
			{
				register int x2 = route[x1][i];
				order.push_back(make_pair(x1, x2));
				if (--check[x2] <= 0)
					q.push(x2);
			}
		}
		for (register int i = 0, x1, x2; i < order.size(); ++i) {
			x1 = order[i].first, x2 = order[i].second;
			if (dp[x2] < dp[x1] + arr[x2])		dp[x2] = dp[x1] + arr[x2];
		}
		cin >> ans, cout << dp[ans] << endl;
	}
	
	return 0;
}
// *&)*@*

1. 노드들의 간선은 순서대로 정렬되어 있지 않습니다.
2. 또한 2->3이 가는 경우도 있고, 3->2로 가는 경우도 있습니다.
3. 따라서 모든 정보를 받은 후, 그것들을 from->to로 풀어주어야 합니다.
4. 그런데 예로 1->2, 2->3, 1->3 가 있다면, 순서대로 계산했을때 3의 결과가 틀릴 수 있습니다. 즉, 1->2 / 1->3 / 2->3 순서로 3이 계산되어야 합니다.
5. 1번을 시작점이라고 하면, 1에서 갈수있는 방법은 2,3 두가지가 있습니다.
6. 따라서 from->to가 2개 이상인 경우에 대해서 먼저 계산을 해준다는 형태로 구현하였습니다.