백준 2056번 작업

문제 링크입니다: www.acmicpc.net/problem/2056

2056번: 작업

N: 수행해야할 작업 -> 범위: 3 <= N <= 10,000

작업마다 걸리는 시간 -> 범위: 1 ~ 100

inDegree: 선행해야할 작업의 수를 저장하는 배열

graph: 작업 단방향 그래프를 나타내는 벡터 배열

result: 최소 시간

delay: 각 작업마다 걸리는 시간을 저장하는 배열

cache: 해당 작업이 완료되는데 걸린 최소 시간을 저장하는 배열

 

알고리즘

1. 작업들을 입력받으면서 graph, delay, inDegree 배열 업데이트

2. inDegree가 없는 작업들 큐에 추가

-> 이 때, cache[i] = delay[i]

3. 위상정렬을 진행하며 cache 업데이트

-> max(cache[next], cache[job] + delay[next])

4. cache 최댓값을 출력하고 프로그램 종료

 

	#include <iostream>
	#include <vector>
	#include <queue>
	using namespace std;
	const int MAX = 10000 + 100;
	int N;
	int delay[MAX];
	int inDegree[MAX];
	int cache[MAX];
	vector<int> graph[MAX];
	int getMinimumTime(void)
	{
	int result = 0;
	queue<int> q;
	for (int n = 1; n <= N; n++)
	{
	if (inDegree[n])
	{
	continue;
	}
	q.push(n);
	cache[n] = delay[n];
	}
	while (!q.empty())
	{
	int job = q.front();
	q.pop();
	for (int next : graph[job])
	{
	if (--inDegree[next] == 0)
	{
	q.push(next);
	}
	cache[next] = max(cache[next], cache[job] + delay[next]);
	}
	}
	for (int n = 1; n <= N; n++)
	{
	result = max(result, cache[n]);
	}
	return result;
	}
	int main(void)
	{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> N;
	for (int n = 1; n <= N; n++)
	{
	int time, num;
	cin >> time >> num;
	delay[n] = time;
	for (int i = 0; i < num; i++)
	{
	int job;
	cin >> job;
	graph[job].push_back(n);
	inDegree[n]++;
	}
	}
	cout << getMinimumTime() << "\n";
	return 0;
	}

view raw .cpp hosted with ❤ by GitHub

개발환경:Visual Studio 2017

 

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~