백준 14907 (C++) 프로젝트 스케줄링

최초 업로드: 2025-09-25 00:45:12

최근 수정 시간: 2025-09-25 00:45:12

게시자: rlatjwls3333

카테고리: 백준

# [Gold II] 프로젝트 스케줄링

[문제 링크](https://www.acmicpc.net/problem/14907)

## 문제 설명

퍼트라고 부르는 프로젝트 관리 기법은 큰 프로젝트를 작업 개수로 분할, 각 작업에서 요구되는 시간 계산, 다른 작업이 완료될 때까지 작업이 시작될 수 없도록 하는 결정을 포함한다. 이때 프로젝트를 차트 형식으로 표현할 수 있다.

예를 들어, 입력 예제의 데이터를 사용했을 때 차트는 A, B, C, D, E, F라는 작업을 갖고 각각 5, 3, 2, 2, 4, 2일이 걸리며, C와 D가 완료될 때까지 작업 E는 시작되지 않고, A가 수행되었다면 D와 B는 병렬로 수행 될 수 있다. 퍼트 차트에 따라 프로젝트를 완성하는데 걸리는 최소 시간을 계산하는 프로그램을 작성하시오.

## 입력

입력은 1줄에서 26줄까지 입력될 수 있으며, 각각은 다른 작업 (위 예제에서 말하자면 A, B, C, …) 을 포함한다. 각 줄에는 다음과 같은 내용이 포함된다.

<ol>
	<li>작업 이름을 나타내는 영문 대문자 하나,</li>
	<li>작업을 완료하는데 요구되는 날짜를 나타내는 1,000보다 작거나 같은 자연수</li>
	<li>0개에서 25개 사이의 덧붙여지는 영문 대문자 (띄어쓰기 없이 붙어 있음)는 이 작업을 시작하기 전에 완료해야만 하는 작업을 나타낸다.</li>
</ol>

항상 모든 작업을 완료할 수 있는 경우만 입력으로 주어진다.

## 출력

첫째 줄에 모든 작업을 완료하는데 걸리는 시간의 최솟값을 출력한다.

## 풀이
입력 받는 것이 가장 어려운 위상 정렬 문제입니다.

``` c++
#include<bits/stdc++.h>
using namespace std;

const int INF = 0x3f3f3f3f;

vector<vector<int>> conn(26);
int inDegree[26], cost[26], maxCost[26];

int main() {
 ios::sync_with_stdio(0); cin.tie(0);
 while(true) {
 string s; getline(cin, s);
 if(cin.fail()) break;
 char a = s[0];
 int i=2, b=0;
 while(i<s.length() && s[i]!=' ') {
 b = b*10 + s[i]-'0';
 i++;
 }

while(++i<s.length()) {
 inDegree[a-'A']++;
 conn[s[i]-'A'].push_back(a-'A');
 }
 cost[a-'A']=b;
 }

queue<int> q;
 for(int i=0;i<26;i++) {
 if(inDegree[i]==0) q.push(i);
 }

while(!q.empty()) {
 int cur = q.front(); q.pop();
 maxCost[cur] += cost[cur];
 for(int next:conn[cur]) {
 maxCost[next] = max(maxCost[next], maxCost[cur]);
 if(--inDegree[next]==0) q.push(next);
 }
 }
 cout << *max_element(maxCost, maxCost+26);
}
```