문제

나의 요약

작업 N개가 있다. 걸리는 시간이 정수로 주어진다.
작업들 사이에는 선행 관계가 존재한다. 물론 없는 작업들도 존재한다. (1번이 그 경우)
선행관계에서 자유로워진 작업들은 동시에 수행 가능하다.
작업을 완료하기 위해 필요한 최소 시간을 출력하자.

접근방법

그냥 사람이 직접 이 문제를 해결한다면 사용할 최적의 방법을 생각했다.
먼저 선행관계가 없는 작업들을 조사해, 작업을 진행한다.
작업이 완료가 되면, 그것을 선행관계로 가지고 있는 작업들의 선행 관계의 수를 -1한다.
선행 관계의 수가 0이 된 작업이 있다면, 작업을 진행할 목록에 저장한다.

진행하는 시간을 1씩 증가시키며 반복하자.

풀이

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

int N;
vector<int> work;
vector<int> relationCount;
vector<vector<int> > relation;

void Input()
{
    cin >> N;
    work.assign(N, 0);
    relationCount.assign(N, 0);
    relation.assign(N, vector<int>());

    for(int i = 0; i < N; i++)
    {
        cin >> work[i];
        cin >> relationCount[i];
        for(int j = 0; j < relationCount[i]; j++)
        {
            int w;
            cin >> w;
            w--;

            relation[i].push_back(w);
            relation[w].push_back(i);
        }
    }
}

void Solve()
{
    int time = 0;

    // 작업번호, 남은 작업시간 
    vector<pair<int, int> > nowWork;

    for(int i = 0; i < N; i++)
    {
        if(relationCount[i] == 0)
        {
            nowWork.push_back({i, work[i]});
        }
    }

    queue<int> justFinishedWork;
    while(!nowWork.empty())
    {
        time++;
        for(vector<pair<int,int> >::iterator it = nowWork.begin(); it != nowWork.end();) 
        {
            (*it).second--;

            if((*it).second == 0) {
                justFinishedWork.push((*it).first);
                it = nowWork.erase(it);
            }
            else 
            {
                it++;
            }
        }

        while(!justFinishedWork.empty())
        {
            int finishedWork = justFinishedWork.front();
            justFinishedWork.pop();

            for(int i = 0; i < relation[finishedWork].size(); i++)
            {
                int relatedWork = relation[finishedWork][i];
                if(relatedWork > finishedWork)
                {
                    
                    relationCount[relatedWork]--;
                    if(relationCount[relatedWork] == 0)
                    {
                        nowWork.push_back({relatedWork, work[relatedWork]});
                    }
                }
            }
        }
    }

    cout << time;

}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    Input();
    Solve();
}

Solve 함수의 첫 while문 부분을 보자. 이 반복문은 현재 작업할 목록이 빌 때까지 지속된다.
시간을 1 증가시키고, 현재 작업 중인 작업들의 남은 시간을 -1 해준다. 만약 남은 시간이 0이 되었다면, 이 작업을 justFinishedWork라고 하는 방금 끝난 작업들 목록에 추가해준다.
이후 justFinishedWork에 들어있는 작업들을 선행관계로 가지는 작업의 남은 선행관계 수를 -1한다. 남은 선행관계 수가 0이라면, 작업할 목록에 이 작업을 넣어주면 된다.

회고

작업이 끝나자마자 그 작업과 선행관계에 있는 작업들에게 알려주는 작업을 얼마나 효율적으로 하느냐가 중요하다고 생각했다. 따로 선행관계 목록을 지우고 하면 그 부분에서 시간이 굉장히 많이 소모될 것이라고 생각했다. 따라서 그냥 선행관계 수만 비교해 시간을 최소화하고자 했다.
사실 내가 클라이언트 개발이라 그런가.. 이런 문제가 나오면 그대로 구현하는 게 재밌는 것 같다. 그대로 구현하다가 작동 시간이 너무 오래걸리는 경우도 있는데, 이 문제 같은 경우엔 그 부분을 신경써서 구현하니 괜찮았다.