[C++]백준 2056번: 작업

#include<iostream>
#include<vector>
#include<queue>

using namespace std;

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int N;
	cin >> N;
	vector<int> time(N+1 , -1);

	vector<int> ttime(N + 1, -1);
	vector<int> indice(N + 1, 0);
	vector<vector<int>> adj(N + 1, vector<int>());
	for ( int i = 1; i < N + 1; i++ ) {
		int du, cnt;
		cin >> du >> cnt;
		time[i] = du;
		for ( int j = 0; j < cnt; j++ ) {
			int tmp;
			cin >> tmp;
			adj[tmp].emplace_back(i);
			indice[i] = cnt;
		}
	}
	queue<int> que;
	for ( int i = 1; i < N + 1; i++ ) {
		if ( indice[i] == 0 ) {
			que.push(i);
			ttime[i] = time[i];
		}
	}
	while ( !que.empty() ) {
		int t = que.front();
		que.pop();
		for ( int d : adj[t] ) {
			indice[d]--;
			ttime[d] = max(ttime[d], time[d] + ttime[t]);
			if ( indice[d] == 0 ) {
				que.push(d);
			}
		}
	}
	int total = 0;
	for ( int i = 1; i < N + 1; i++ ) {
		total = max(total, ttime[i]);
	}
	cout << total << endl;
	return 0;
}

풀이

위상정렬을 통해 문제를 해결하였다. time vector에는 input으로 주어지는 고정시간이 들어가고 ttime vector에는 해당 작업에 선제 되는 작업들 중 가장 오래 걸린 작업의 시간을 넣는다. indice값이 0이 되면 선제 작업이 모두 끝났으므로 해당 작업을 queue에 넣는다. queue에 더 이상 원소가 없을 때까지 즉 모든 작업이 queue에 들어갔다 나올 때까지 반복한다.