BOJ 14907 - 프로젝트 스케줄링 링크
(2024.05.24 기준 G2)

문제

각 프로젝트는 처리 시간과 시작하기 위해 완료되어야 하는 선행 프로젝트가 정해져 있다.
모든 프로젝트를 완료하는데 걸리는 최소 시간 출력

알고리즘

전형적인 위상 정렬 + DP 문제

풀이

$A$라는 프로젝트가 $B$, $C$라는 선행 프로젝트가 필요하다고 가정하자.

$T(u)$는 프로젝트 $u$의 처리 시간, $dp(u)$를 프로젝트 $u$를 완료하는 최소 시간이라고 정의했을 때
$dp(A) = max(dp(B), dp(C)) + T(A)$ 이라는 점화식을 세울 수 있다.

$A$는 $B$, $C$가 전부 완료되어야 시작할 수 있으니, $B$와 $C$가 완료되는 시각 중 가장 늦은 시각부터 $A$를 처리할 수 있기 때문이다.

그러므로 선행 프로젝트가 없는 프로젝트를 찾아서 순서대로 처리하는 식으로 위상 정렬을 진행하면서 dp 테이블을 채워나가면 된다.

이 문제는 사실 입력 조건이 좀 까다롭다. 그래서 알고리즘 자체는 동일한 ACM Craft보다 난이도가 1 더 높다. 입력 부분은 코드를 참고하자.

코드

• C++

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

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    map<char, int> ctoi; // 각 알파벳마다 번호 부여
    vector<vector<int>> G; // 그래프
    vector<int> T; // 각 정점의 시간

    int N = 0; // 정점의 개수
    string line;
    while (getline(cin, line)){
        vector<char> vertex;
        int t = 0;
        for (char c: line){
            if (c == ' ') continue;
            if ('A' <= c) vertex.push_back(c);
            else t = t * 10 + c - '0';
        }

        if (vertex.size() == 1){
            if (ctoi.find(vertex[0]) == ctoi.end()){ // 나온 적 없는 알파벳이면 번호를 부여한다.
                ctoi[vertex[0]] = N++;
                G.push_back({});
                T.push_back(t);
            }
            else T[ctoi[vertex[0]]] = t;
        }

        else{
            if (ctoi.find(vertex[0]) == ctoi.end()){ // 나온 적 없는 알파벳이면 번호를 부여한다.
                ctoi[vertex[0]] = N++;
                G.push_back({});
                T.push_back(t);
            }
            else T[ctoi[vertex[0]]] = t;
            for (int i = 1; i < vertex.size(); i++){
                if (ctoi.find(vertex[i]) == ctoi.end()){ // 나온 적 없는 알파벳이면 번호를 부여한다.
                    ctoi[vertex[i]] = N++;
                    G.push_back({});
                    T.push_back(0);
                }
                G[ctoi[vertex[i]]].push_back(ctoi[vertex[0]]); // 유향 간선
            }
        }
    }

    // 위상 정렬을 위해 각 정점마다 진입 차수를 계산한다.
    int ind[N]; memset(ind, 0, sizeof(ind));
    for (int u = 0; u < N; u++) for (int v: G[u]) ++ind[v];

    // 진입 차수가 0인 정점을 찾아 스택에 담는다.
    stack<int> stk;
    for (int u = 0; u < N; u++) if (!ind[u]) stk.push(u);

    int dp[N]; memset(dp, 0, sizeof(dp));
    while (!stk.empty()){
        int u = stk.top(); stk.pop();
        dp[u] += T[u]; // 현재 정점에서 걸리는 시간을 더해준다.
        for (int v: G[u]){
            dp[v] = max(dp[v], dp[u]); // v로 진입하는 시각 중 가장 늦은 시각부터 v를 처리할 수 있다.
            if (!--ind[v]) stk.push(v); // v로 진입하는 정점 모두 처리가 완료되었다면 v를 처리할 수 있다.
        }
    }

    int ans = 0;
    for (int u = 0; u < N; u++) ans = max(ans, dp[u]);
    cout << ans;
}

• Python

import sys; input = sys.stdin.readline

ctoi = dict() # 각 알파벳마다 번호 부여
G = [] # 그래프
T = [] # 각 정점의 시간

N = 0 # 정점의 개수
while True:
    query = input().split()

    if len(query) == 2:
        u, t = query
        if u not in ctoi: # 나온 적 없는 알파벳이면 번호를 부여한다.
            ctoi[u] = N
            N += 1
            G.append([])
            T.append(int(t))
        else:
            T[ctoi[u]] = int(t)

    elif len(query) == 3:
        u, t, s = query
        if u not in ctoi: # 나온 적 없는 알파벳이면 번호를 부여한다.
            ctoi[u] = N
            N += 1
            G.append([])
            T.append(int(t))
        else:
            T[ctoi[u]] = int(t)
        for c in s:
            if c not in ctoi: # 나온 적 없는 알파벳이면 번호를 부여한다.
                ctoi[c] = N
                N += 1
                G.append([])
                T.append(0)
            G[ctoi[c]].append(ctoi[u]) # 유향 간선

    else:
        break

# 위상 정렬을 위해 각 정점마다 진입 차수를 계산한다.
ind = [0] * N
for u in range(N):
    for v in G[u]:
        ind[v] += 1

# 진입 차수가 0인 정점을 찾아 스택에 담는다.
stk = []
for u in range(N):
    if not ind[u]:
        stk.append(u)

dp = [0] * N
while stk:
    u = stk.pop()
    dp[u] += T[u] # 현재 정점에서 걸리는 시간을 더해준다.
    for v in G[u]:
        dp[v] = max(dp[v], dp[u]) # v로 진입하는 시각 중 가장 늦은 시각부터 v를 처리할 수 있다.
        ind[v] -= 1
        if not ind[v]: # v로 진입하는 정점 모두 처리가 완료되었다면 v를 처리할 수 있다.
            stk.append(v)

print(max(dp))