2056 작업

2056번: 작업

 

DP와 DFS를 활용하여 해결했다.

각 작업을 노드로, 그리고 각 작업과 선행작업을 방향이 있는 간선으로 연결했다.

그래프를 구성한 다음에는 각 노드에 연결된 선행 작업들을 DFS 방식으로 순회하며 최대 작업 시간을 가진

노드를 찾고, 그 노드의 작업시간과 해당 노드의 수행 시간을 더해 작업시간으로 정했다.

그리고 이 과정에서 각 노드의 작업시간을 구하면 메모리제이션을 이용하여 한번만 찾도록 했다.

이 과정을 수행하면서 모든 작업을 완료하기 위한 최소 시간을 구하여 출력했다.

#include <iostream>
#include <vector>

using namespace std;

int minimum_time = -1;

int search(vector<pair<int, vector<int>>>& jobs, vector<int>& times, int target) {
	int& target_time = times[target];
	if (target_time == -1) {
		if (jobs[target].second.size() != 0) {
			int time = -1;
			for (auto prev : jobs[target].second)
				time = max(time, search(jobs, times, prev));
			target_time = time + jobs[target].first;
		}
		else
			target_time = jobs[target].first;
		if (minimum_time < target_time)
			minimum_time = target_time;
	}
	return target_time;
}

int main(void)
{
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);

	int n;
	cin >> n;

	vector<pair<int,vector<int>>> jobs(n + 1);
	vector<int> times(n + 1, -1);

	for (int i = 1, time, nums; i <= n; ++i) {
		cin >> time >> nums;
		jobs[i].first = time;
		jobs[i].second = vector<int>(nums);
		for (int j = 0; j < nums; ++j)
			cin >> jobs[i].second[j];
	}

	for (int i = 1; i <= n; ++i)
		search(jobs, times, i);

	cout << minimum_time;
	
	return 0;
}