[BOJ알고리즘, C++]#2056_작업, 위상 정렬, 비순환 유향 그래프, DAG

 

#1. 문제

2056번: 작업

 

---

 

#2. 풀이

 

1. 위상 정렬

[자료구조]#6_그래프

 

위상 정렬은 비순환 유향 그래프에서 각 정점의 선행 관계를 유지하며 정점들을 나열하는 방법입니다. 일반적으로, 위상 정렬은 DFS와 진입차수 BFS를 활용하여 구현합니다.

 

2. 위상 정렬과 더불어 이에 걸리는 최소 시간 등의 문제가 많이 나온다!

 

1. 단순히, 선행 관계를 유지하며 나열하는 방법은 위상 정렬 알고리즘을 활용하면 됩니다.
2. 이때, 선행 관계를 유지하여 나열하였을 경우, 각 정점에 작업 처리 시간 등이 주어지며, 모든 작업을 처리하기 위해 걸리는 최소 시간을 구하는 등의 추가 조건이 붙는 문제가 많다.
3. 각 정점의 작업 처리 시작 시간 혹은 끝나는 시간 등을 기억하는 별도의 vector 컨테이너를 선언합니다.
4. 위상 정렬 알고리즘에서, 현재 정점의 인접 정점들을 차례대로 순회합니다. 이때, 인접 정점의 작업 시작 시간과 현재 정점의 작업이 끝난 시간을 비교하여, 이를 최대 값으로 갱신하는 코드를 추가적으로 작성해 줍니다.
5. 결과적으로, BFS를 수행하는 과정에서 "현재 정점"과 관련된 값을 통해 "인접 정점"과 관련된 값을 경신해 주며, 마지막에 갱신된 값을 찾아주면 됩니다!

 

---

 

#3. 코드

 

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

int N;
vector<vector<int>> graph;
vector<int> time, InDegree;
int maxFinishTime = INT_MIN;

int TopologicalSort()
{
    queue<int> q;
    vector<int> startTime(N + 1, 0);

    for (int i = 1; i <= N; ++i)
    {
        if (InDegree[i] == 0)
            q.push(i);
    }

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

        // 작업 종료 시간
        time[cur] += startTime[cur];
        if (maxFinishTime < time[cur])
            maxFinishTime = time[cur];

        for (const auto &neighbor : graph[cur])
        {
            InDegree[neighbor]--;
            startTime[neighbor] = max(startTime[neighbor], time[cur]);

            if (InDegree[neighbor] == 0)
            {
                q.push(neighbor);
            }
        }
    }

    return maxFinishTime;
}

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

    cin >> N;

    graph.resize(N + 1);
    time.resize(N + 1, 0);
    InDegree.resize(N + 1, 0);

    for (int from = 1; from <= N; ++from)
    {
        cin >> time[from];

        int num;
        cin >> num;

        while (num--)
        {
            int to;
            cin >> to;

            graph[from].push_back(to);
            InDegree[to]++;
        }
    }

    cout << TopologicalSort();

    return 0;
}

 

---