[C++] 백준 14907번: 프로젝트 스케줄링

문제 링크

14907번: 프로젝트 스케줄링

문제 요약

PERT 차트에 따라서 작업을 수행한다. PERT 차트에서는 선수작업이 모두 끝나야 다음 작업을 진행할 수 있다. 이때, 모든 작업을 완료하는데 걸리는 시간을 구해야 한다.

접근 방법

소프트웨어를 전공하는 분이라면 한번쯤은 들어보셨을 법한 PERT 차트에 대한 문제입니다.

문제를 그래프로 볼 수 있는데, 정점의 수가 26개 정도밖에 없기 때문에 다양한 풀이로 풀 수 있습니다.

제 경우에는 이 문제가 DAG(유향 비순환 그래프)임을 이용해서 위상정렬로 풀었습니다.
각 작업을 하는데 걸리는 시간을 저장하는 배열, 그래서 실제로 작업이 끝나는 시간을 저장하는 배열, 마지막으로 진입차수를 기록할 배열이 필요합니다.

그래프를 인접 리스트를 통해서 정의해준 다음에(이 과정에서 진입차수도 기록을 해줍니다.), 진입차수가 0인 정점들부터 큐에 넣고 방문을 해줍니다. 진입차수가 0인 정점들은 실제로 작업이 끝나는 시간과, 작업에 소모되는 시간이 동일합니다.

이제 방문한 정점에서 방문이 가능한 정점들의 작업이 끝나는 시간을 갱신해줍니다. 이 때, (현재 정점에서 작업이 끝나는 시간) + (방문하는 정점의 작업 시간)의 최댓값을 구해서 저장해주면 됩니다. 그리고 그 정점의 진입차수를 1 감소시켜 주는데, 만약 이 때 진입차수가 0이 되면 이 정점도 큐에 넣어주면 됩니다. 이렇게 해서 모든 정점의 작업이 끝나는 시간을 구할 수 있습니다.

문제 자체는 매우 쉬운 전형적인 위상정렬 문제인데, 입력을 처리하는 부분이 특이해서 조금 번거로운 문제였습니다.

코드

#include <bits/stdc++.h>

using namespace std;

int main(void) {
	int t[26], f[26] = { 0, }, degree[26];
	vector<int> adj[26];

	string str;
	while(getline(cin, str)) {
		string tmp = "";
		vector<string> v;
		for (auto& i : str) {
			if (i != ' ')
				tmp.push_back(i);
			else
				v.push_back(tmp), tmp = "";
		}
		v.push_back(tmp);

		char task = v[0][0];
		int day = stoi(v[1]);
		string tasks = (v.size() == 2 ? "" : v[2]);

		for (auto& j : tasks)
			adj[j - 'A'].push_back(task - 'A');
		degree[task - 'A'] = tasks.size();
		t[task - 'A'] = day;
	}

	queue<int> q;

	for (int i = 0; i < 26; i++) {
		if (t[i] && !degree[i]) {
			q.push(i);
			f[i] = t[i];
		}
	}

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

		for (auto& next : adj[now]) {
			f[next] = max(f[next], f[now] + t[next]);

			if (!--degree[next])
				q.push(next);
		}
	}

	int ans = 0;
	for (int i = 0; i < 26; i++)
		ans = max(ans, f[i]);

	cout << ans << '\n';
	return 0;
}