[백준] 2056 작업 c++

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

2056번: 작업

 

풀이과정

dp와 위상 정렬을 같이 쓰는 문제이며 1005 ACM Craft 문제와 비슷한 문제이다. 

이처럼 위상정렬과 dp가 같이 쓰이는 문제가 많은 것 같다.

풀이 과정은 1005번 문제와 같지만, 처음에 입력문에서 v를 푸시하는 과정에서 반대로 푸시를 해 고생을 먹었던 문제이다. 몇 번 노드에 몇 번 노드를 푸시해줄 것인지 방향을 잘 생각해서 입력받아야 한다.

도착점이 정해져있지 않으므로 res값 중 가장 큰 값을 출력한다.

 

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

int N, M, x;
int t[10001];
int indegree[10001]; // 진입차수
int res[10001];

queue <int> q;
vector <int> v[10001];

void topologySort() {
	for (int i = 1; i <= N; i++) {
		if (indegree[i] == 0) {
			q.push(i);
			res[i] = t[i];
		}
	}

	while (!q.empty()) {
		int now = q.front();
		q.pop();

		for (int i = 0; i < v[now].size(); i++) {
			int next = v[now][i];
			indegree[next]--;

			res[next] = max(res[next], res[now] + t[next]);
			if (indegree[next] == 0) q.push(next);
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	cin >> N;
	for (int i = 1; i <= N; i++) {
		cin >> t[i] >> indegree[i];
		for (int j = 0; j < indegree[i]; j++) {
			cin >> x;
			v[x].push_back(i);
		}
	}
	topologySort();

	int ans = 0;
	for (int i = 1; i <= N; i++) {
		ans = max(ans, res[i]);
	}
	cout << ans;
}