백준 2056 - 작업

문제 설명

수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다.

몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해 반드시 먼저 완료되어야 할 작업들이 있다. 이 작업들은 번호가 아주 예쁘게 매겨져 있어서, K번 작업에 대해 선행 관계에 있는(즉, K번 작업을 시작하기 전에 반드시 먼저 완료되어야 하는) 작업들의 번호는 모두 1 이상 (K-1) 이하이다. 작업들 중에는, 그것에 대해 선행 관계에 있는 작업이 하나도 없는 작업이 반드시 하나 이상 존재한다. (1번 작업이 항상 그러하다)

모든 작업을 완료하기 위해 필요한 최소 시간을 구하여라. 물론, 서로 선행 관계가 없는 작업들은 동시에 수행 가능하다.

---

 

 

 

 

 

 

제한 사항

---

 

 

 

 

 

 

풀이

문제를 요약하면, N개의 작업이 주어지고 각 작업은 선행 작업이 있어 선행 작업이 모두 완료되어야지만 해당 작업을 수행할 수 있다.

이때, 모든 작업을 끝마치는 최소 시간을 구하는 것이다.

 

문제 설명을 보면 힌트가 굉장히 많이 있다.

"선행과 후행 작업이 명확하고 선행 작업이 없는 작업이 무조건 존재한다."

이 조건은 위상 정렬을 활용하기 최적의 조건이다.

 

선행 작업이 없는 작업들을 큐에 넣고 해당 작업이 종료되면 수행할 수 있는 후행 작업들에게 작업이 끝났음을 알려주면 된다.

이때, 후행 작업의 선행 작업이 모두 완료된다면 그 작업도 큐에 넣고 반복하면 된다.

여기서 두 가지 팁이 있다.

나는 이 논리를 구현하기 위해 구조체를 만들었는데 처음에는 set으로 선행 작업과 후행 작업을 관리했다.

struct Task
{
    int duration;
    int endTime;
    set<int> preTasks;
    set<int> postTasks;

    Task(int d): duration(d), endTime(0)
    {

    }
};

하지만 위상 정렬은 선행 작업이 어떤 작업인지는 중요하지 않다.

중요한 것은 선행 작업의 개수이다.

따라서, 다음과 같이 변경할 수 있다.

struct Task
{
    int duration;
    int endTime;
    int preTasks;
    vector<int> postTasks;

    Task(int d): duration(d), endTime(0)
    {

    }
};

후행 작업을 관리하는 이유는 선행 작업이 완료되었을 때 후행 작업들에게 알리기 위해 미리 저장해 놓는 것이다.

void Topology()
{
    while (!q.empty())
    {
        auto idx = q.front();
        q.pop();

        for (auto& post : tasks[idx].postTasks)
        {
            tasks[post].preTasks--;
            tasks[post].endTime = max(tasks[post].endTime, tasks[idx].endTime + tasks[idx].duration);

            if (tasks[post].preTasks == 0)
            {
                q.push(post);
            }
        }
    }
}

 

---

 

 

 

 

 

전체 코드

#include <bits/stdc++.h>
#include <unordered_set>
using namespace std;
#define INPUT_OPTIMIZE cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define INF 2e9

using namespace std;
int N;
struct Task
{
    int duration;
    int endTime;
    int preTasks;
    vector<int> postTasks;

    Task(int d): duration(d), endTime(0)
    {

    }
};

vector<Task> tasks;
queue<int> q;

void Topology()
{
    while (!q.empty())
    {
        auto idx = q.front();
        q.pop();

        for (auto& post : tasks[idx].postTasks)
        {
            tasks[post].preTasks--;
            tasks[post].endTime = max(tasks[post].endTime, tasks[idx].endTime + tasks[idx].duration);

            if (tasks[post].preTasks == 0)
            {
                q.push(post);
            }
        }
    }
}

int main() 
{
    INPUT_OPTIMIZE;

    /*
    * 선행 작업이 없으면 바로 수행(동시 가능)
    * 선행 작업은 무조건 자신보다 번호가 작음
    * 1번은 항상 선행이 없음
    * 선행이 없는건 하나 이상
    * 
    * 선행이 자신보다 무조건 작다 -> 선행이 모두 끝나야 해당 작업이 가능
    * 위상 정렬?
    * 
    * 선행, 후행을 모두 기록
    * 선행이 0이면 q에 추가
    * q에 들어간 애들은 자신의 후행에서 pre를 제거해줌
    * 제거해주면서 pre가 0이되면 q에 추가
    * 끝나는 시간을 같이 기록 -> 끝나는 시간은 max값으로 갱신
    */

    cin >> N;

    //0 -> index맞추기
    tasks.push_back(Task(0));


    for (int i = 1; i <= N; i++)
    {
        int d, p;
        cin >> d >> p;

        tasks.push_back(Task(d));

        tasks[i].preTasks = p;
        
        for (int j = 0; j < p; j++)
        {
            int t;
            cin >> t;
            tasks[t].postTasks.push_back(i);
        }

        if (tasks[i].preTasks == 0)
        {
            q.push(i);
        }
    }

    Topology();

    int ans = 0;
    int idx = 1;
    for (int i =1; i <= N; i++)
    {
        ans = max(ans, tasks[i].endTime + tasks[i].duration);
    }

    cout << ans;

    return 0;
}

---