boj-2056.md

---
layout    : wiki
title     : BOJ 2056. 작업
summary   : 
date      : 2021-03-11 09:02:56 +0900
updated   : 2021-12-15 17:59:27 +0900
tag       : 
public    : true
published : true
parent    : [[boj]]
latex     : false
---
* TOC
{:toc}

- 선행이 필요하기 때문에 topological sort
- 최소 시간을 물어봤지만, 최댓값을 구해야 한다.
- maxSum[from] 들중 최댓값을 maxSum[to]에 저장하고, maxSum이 pop되면 그때 해당 작업의 weight를 추가해준다.
- indegree[to]가 0일 때만 queue에 push하면 되는데, to를 만날 때마다 queue에 push하고 꺼낼 때 해당 indegree가 0인지 여부를 확인하는 과정을 넣는 바람에 메모리 초과가 발생했다. 

```cpp linenos
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string>
#include <functional>
#include <vector>
#include <queue>

using namespace std;

#define MAX_N 10010

int N;
vector<int> edge[MAX_N];
int indegree[MAX_N];
int weight[MAX_N];
int maxSum[MAX_N];

void solution() {
	queue<int> q;
	for (int from = 1; from <= N; from++)
		if (indegree[from] == 0)
			q.push(from);

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

		maxSum[from] += weight[from];

		for (int i = 0; i < edge[from].size(); i++) {
			int to = edge[from][i];

			maxSum[to] = max(maxSum[to], maxSum[from]);
			indegree[to]--;
			if (indegree[to] == 0)
				q.push(to);
		}
	}
}

int main() {
	fill_n(maxSum, MAX_N, 0);

	scanf("%d", &N);
	for (int to = 1; to <= N; to++) {
		scanf("%d", &weight[to]);

		int M;
		scanf("%d", &M);
		for (int j = 0; j < M; j++) {
			int from;
			scanf("%d", &from);
			edge[from].push_back(to);
			indegree[to]++;
		}
	}
	solution();

	int res = 0;
	for (int i = 1; i <= N; i++)
		res = max(res, maxSum[i]);
	printf("%d\n", res);
}
```