[백준 2056번] 작업

문제 링크: https://www.acmicpc.net/problem/2056

2056번: 작업

 

<문제 풀이> 다이나믹 프로그래밍(DP), 위상정렬 알고리즘

 

작업에는 순서가 있으므로 위상정렬을 사용해야 합니다. 또한, 모든 작업을 완료하기 위한 최소 시간을 구하기 위해 DP를 활용해야 합니다.

DP의 정의는 아래와 같습니다:

 

DP[i] : i번째 작업이 완료되는 데 필요한 최소 시간

 

위상 정렬을 수행하며 현재 작업에 연결된 다음 작업들의 최소 완료 시간을 갱신해 나갑니다. 현재 작업을'cur', 그에 연결된 다음 작업을 'next'라고 할 때, 'next'작업의 최소 완료 시간은 아래와 같이 계산합니다:

dp[next] = max(dp[next], dp[cur] + t[next]);

 

여기서 max함수를 사용하는 이유는 다음 작업에 대한 선행 작업들 중에서 최소 완료 시간이 가장 긴 작업이 그 작업의 완료 시간에 영향을 주기 때문입니다.

 

예를 들어, A 작업이 5분, C 작업이 3분이 걸린다고 할 때, B 작업을 시작하기 위해선 A작업이 완료되어야 합니다.

 

A(5분) -> B

B(3분) -> B

 

<C++소스코드>

 

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

vector<int> adj[10001];
int indegree[10001];
int t[10001];
int dp[10001];
int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	
	int n; cin >> n;
	for (int u = 1; u <= n; u++) {
		cin >> t[u];
		int m; cin >> m;
		while (m--) {
			int v; cin >> v;
			adj[v].push_back(u);
			indegree[u]++;
		}
	}
	queue<int> Q;
	for (int u = 1; u <= n; u++){
		if (indegree[u] == 0) {
			Q.push(u);
			dp[u] = t[u];
		}
	}
	while (!Q.empty()) {
		auto cur = Q.front(); Q.pop();
		for (auto next : adj[cur]) {
			indegree[next]--;		
			dp[next] = max(dp[next], dp[cur] + t[next]);
			if (indegree[next] == 0) {
				Q.push(next);
			}
		}
	}
	cout << *max_element(dp + 1, dp + 1 + n);
	return 0;
}