[백준] 2056 작업

백준 2056 작업

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

풀이

• 틀렸던 접근 방식:
  현재 작업이 끝나는 시간 = 선행해야하는 작업 중 가장 마지막 번호의 작업이 끝나는 시간 + 현재 작업에 필요한 시간
  jobFinishedTime[i] = jobFinishedTime[requiredJob[i]] + requiredTime[i];

• 선행해야하는 작업 중 가장 마지막 번호의 작업이 가장 늦게 끝난다는 보장이 없으므로, 선행해야하는 모든 작업이 끝나는 시간에 대해 고려해야 한다

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

const int MAXN = 10001;

int N;
//index 1~N
vector<vector<int>> work(MAXN, vector<int>(1,0));
int time[MAXN];
int finish[MAXN] = { 0 };

int getFinishTime() {
	int ret = 0;

	for (int i = 1; i <= N; ++i){

		int lastFinish = 0;
		while (!work[i].empty()) {
			lastFinish = max(lastFinish, finish[work[i].back()]);
			work[i].pop_back();
		}
			
		finish[i] = lastFinish + time[i];
		ret = max(ret, finish[i]);
	}


	return ret;
}

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

	cin >> N;
	for (int i = 1; i <= N; ++i) {
		cin >> time[i];

		int n; 
		cin >> n;
		for (int j = 1; j <= n; ++j) {
			int w;
			cin >> w;
			work[i].push_back(w);
		}
	}
	
	cout << getFinishTime();
	return 0;
}

⚡ 위상 정렬 풀이

• 선후 관계가 있는 문제이므로 위상 정렬 알고리즘을 사용하여 풀이할 수 있다

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

const int MAXN = 10001;

int n;
int inDegree[MAXN] = { 0 };
int time[MAXN] = { 0 };
vector<int> child[MAXN];

//dp[node]
int dp[MAXN] = { 0 };

int topologySort() {
	//pair<node>
	queue<int> q;

	for (int i = 1; i <= n; ++i)
		if (inDegree[i] == 0) {
			dp[i] = time[i];
			q.push(i);
		}

	for (int i = 1; i <= n; ++i ){
		if (q.empty()) break;

		int parent = q.front();
		q.pop();

		for (int i = 0; i < child[parent].size(); ++i) {
			int childnode = child[parent][i];

			dp[childnode] = max(dp[childnode], dp[parent] + time[childnode]);

			if (--inDegree[childnode] == 0) {
				q.push(childnode);
			}
		}
	}

	int res = 0;
	for (int i = 1; i <= n; ++i)
		res = max(res, dp[i]);

	return res;
}


int main(){

	cin >> n;

	for (int i = 1; i <= n; ++i) {
		cin >> time[i];
		cin >> inDegree[i];
		for (int j = 0; j < inDegree[i]; ++j) {
			int parent;
			cin >> parent;
			child[parent].push_back(i);
		}
	}

	cout << topologySort();
	return 0;
}

📌참고자료

• 백준 2056 작업 풀이
  https://jaimemin.tistory.com/1525