[백준 BOJ 2056 gold4 - 작업] 위상정렬(topological sort) C++

 

백준 2056 작업

 

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

2056번: 작업

 

위상정렬 문제이다. 

1516 게임개발 문제와 매우 비슷하다. 

https://steptoprogrammer.tistory.com/57

[백준 BOJ 1516 gold3 - 게임 개발] 위상정렬(topological sort) C++

 

게임개발에서는 건물 각각을 짓는데 필요한 시간을 구했다면, 여기서 가장 큰 값을 출력하는 것이 이 문제의 해답이 된다. (모든 작업을 완료하는데 걸리는 최소 시간을 구해야 하므로)

 

#include<iostream>
#include<string>
#include<algorithm>
#include<string.h>
#include<string>
#include<vector>
#include<queue>

using namespace std;

int N;
int indegree[10001];
vector<int> v[10001];
int period[10001];
int dab[10001];
queue <int> q;

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

	cin >> N;
	for (int i = 1; i <= N; i++) {
		int x;
		cin >> period[i];
		cin >> x;
		for (int j = 1; j <= x; j++) {
			int k;
			cin >> k;
			v[k].push_back(i);
			indegree[i]++;
		}
	}
	for (int i = 1; i <= N; i++) {
		if (indegree[i] == 0) q.push(i);
		dab[i] = period[i];
	}

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

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

			dab[next] = max(dab[next], dab[top] + period[next]);
			if (indegree[next] == 0) q.push(next);
		}
	}
	int larg = 0;
	for (int i = 1; i <= N; i++) {
		if (dab[i] > larg) larg = dab[i];
	}
	cout << larg;
}