[백준/BOJ] 백준 14907번 : 프로젝트 스케줄링

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

14907번: 프로젝트 스케줄링

 

작업의 관계를 그래프로 표현하고 위상정렬과 같은 방법을 통해 탐색해 나아가며, 작업을 시작하려면 해당 작업에 영향을 주는 다른 작업들을 모두 마쳐야 시작이 될 수 있는데, 해당 작업을 시작하는 시간은 해당 작업에 영향을 주는 다른 작업들 중 끝나는 시간이 가장 늦은 작업이 끝나는 시간이라는 것을 이용해서 문제를 해결했다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <string>
#include <sstream>
using namespace std;

vector<int> cost(30, 0);
vector<int> adj[30];
vector<int> indegree(30, 0);
vector<long long> cache(30, -1);
queue<int> q;

int main()
{
	while (1) {
		string input1;
		getline(cin, input1);

		if (cin.eof()) {
			break;
		}

		vector<string> input2;
		stringstream ss(input1);
		string temp;
		while (getline(ss, temp, ' ')) {
			input2.push_back(temp);
		}

		cost[input2[0][0] - 'A'] = stoi(input2[1]);

		if (input2.size() == 2) {
			continue;
		}

		for (int i = 0; i < input2[2].size(); i++) {
			adj[input2[2][i] - 'A'].push_back(input2[0][0] - 'A');
			indegree[input2[0][0] - 'A']++;
		}
	}

	long long result = -1;

	for (int i = 0; i < 30; i++) {

		if (indegree[i] == 0 && cost[i] != 0) {
			cache[i] = (long long)cost[i];
			result = max(result, cache[i]);
			q.push(i);
		}
	}

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

		for (int i = 0; i < adj[here].size(); i++) {
			int there = adj[here][i];

			indegree[there]--;

			cache[there] = max(cache[there], cache[here] + (long long)cost[there]);
			result = max(result, cache[there]);

			if (indegree[there] == 0) {
				q.push(there);
			}
		}
	}

	cout << result;

	return 0;
}