백준 2056번 작업 (C++)

백신 맞고 죽는 줄 알았다.
이번 문제는 위상 정렬 문제이다.
이번 주에 문제를 거의 못 풀어서 너무 가볍지도 무겁지도 않은 문제를 택했다.

문제링크
https://www.acmicpc.net/problem/2056

설명

위상 정렬 문제에서는 늘 따로 저장해야 할 정보가 많다.
위 문제에서는 다음과 같다.
1. 위 작업의 작업 시간은 얼마나 걸리는가?
2. 위 작업의 선행 작업은 총 몇 개 인가?
3. 위 작업을 완료해야 진행할 수 있는 작업에는 무엇이 있는가?

선행 작업의 개수가 0인 작업들만 큐에 넣어서 완료시켜준 뒤, 위 작업을 완료해야만 진행될 수 있는 작업을 큐가 빌 때까지 차례로 진행시킨다.

위 문제에서는 정석적인 위상정렬 코드를 사용하고도 WA를 받았는데, 이는 아래와 같은 반례를 큐를 사용하고 해결할 수 없기 때문이다.

1번 작업시간 -> 6초
2번 작업시간 -> 3초
3번 작업시간 -> 1초, 선행되어야 할 작업 -> 1, 2

위와 같은 예제에서는 답이 7초(1번 작업시간 + 3번 작업시간)이어야 하는데 큐를 사용하면 4초가 나온다.

보통 선행 작업의 개수가 0인 작업들을 큐에 넣어줄 때, 1번 작업부터 N번 작업까지 순서대로 넣어주기 때문에 이와 같은 상황이 발생한다.

그래서 우선순위큐를 사용하여 작업시간이 적은 순서대로 큐에 넣어주었고, AC를 받을 수 있었다.

코드

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

using namespace std;

int main(void)
{
	int n, time, pre, work, nextwork, ans = 0;
	cin >> n;
	vector<int> pretask(n + 1), tasktime(n + 1);
	vector<vector<int>> nexttask(n + 1);
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> working;
	for (int i = 1; i <= n; i++)
	{
		cin >> time >> pre;
		tasktime[i] = time;
		while (pre--)
		{
			cin >> work;
			pretask[i]++;
			nexttask[work].push_back(i);
		}
	}
	for (int i = 1; i <= n; i++)
	{
		if (!pretask[i])
			working.push(make_pair(tasktime[i], i));
	}
	while (!working.empty())
	{
		time = working.top().first;
		work = working.top().second;
		working.pop();

		ans = max(ans, time);

		for (int i = 0; i < nexttask[work].size(); i++)
		{
			nextwork = nexttask[work][i];
			pretask[nextwork]--;
			if (!pretask[nextwork])
				working.push(make_pair(time + tasktime[nextwork], nextwork));
		}
	}
	cout << ans;
	return 0;
}