[백준 2056번] 작업 (C++)

문제링크 : https://www.acmicpc.net/problem/2056

2056번: 작업

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

vector<int>inDegree, v, result;
vector<vector<int>>graph;
int N, num, task, ans;

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

    cin >> N;
    result.resize(N+1);
    v.resize(N+1);
    inDegree.resize(N+1);
    graph.resize(N+1);

    for(int i=1; i<=N; i++)
    {
        cin >> v[i] >> num;
        for(int j=0; j<num; j++)
        {
            cin >> task;
            graph[task].push_back(i);
            inDegree[i]++; //진입 차수 증가 
        }
    }

    queue<int>q;
    for(int i=1; i<=N; i++) //진입차수가 0인 정점들을 큐에 삽입
    {
        if(inDegree[i]==0) q.push(i);
        result[i]=v[i];
    }

    for(int i=0; i<N; i++)
    {
        if(q.empty()) break; //큐가 비면 사이클 발생이므로 종료
        int cur = q.front(); //현재 방문 노드
        q.pop();
        ans = max(result[cur], ans);
        for(int j=0; j<graph[cur].size(); j++) //인접한 노드들의 진입 차수를 1씩 줄이고, 0이면 다시 큐에 삽입
        {
            int next = graph[cur][j];
            result[next] = max(result[next], result[cur] + v[next]); //작업시간 갱신
            if(--inDegree[next]==0) q.push(next);
        }
    }
    cout << ans;
    return 0;
}

위상정렬 문제의 응용문제이다.

위상정렬에 대한 내용은 어제 작성했었으므로 이번 문제에서는 스킵하였다.

참고링크 : https://blob-thinking.tistory.com/281

[백준 2252번] 줄 세우기 (C++)

 

해당 문제에서 추가로 고려해야할 것은 작업 순서에 따른 작업시간 갱신이다.

<작업 순서 : 1 2 4 3 5 6 7>

cur : 1, next = 2
작업시간(result[next]) : max(1, 5 + 1) = 6
cur : 1, next = 4
작업시간(result[next]) : max(6, 5 + 6) = 11

cur : 2, next = 3
작업시간(result[next]) : max(3, 6 + 3) = 9
cur : 2, next = 5
작업시간(result[next]) : max(1, 6 + 1) = 7
cur : 2, next = 6
작업시간(result[next]) : max(8, 6 + 8) = 14

cur : 4, next = 5
작업시간(result[next]) : max(7, 11 + 1) = 12
cur : 4, next = 6
작업시간(result[next]) : max(14, 11 + 8) = 19

cur : 3, next = 7
작업시간(result[next]) : max(4, 19 + 4) = 13

cur : 5, next = 7
작업시간(result[next]) : max(13, 12 + 4) = 16

cur : 6, next = 7
작업시간(result[next]) : max(16, 19 + 4) = 23

result[next] = max(result[next], result[cur] + v[next] 해당 수식을 통해서 작업시간을 갱신해준다.

기본적으로 현재 작업시간 + 다음 작업시간을 더해주는데,

해당 작업에 도달하는 경로가 여러가지 이므로 최대 작업시간으로 갱신해준다.

 

문제에서 "K번 작업에 대해 선행 관계에 있는(즉, K번 작업을 시작하기 전에 반드시 먼저 완료되어야 하는) 작업들의 번호는 모두 1 이상 (K-1) 이하"라고 써져있기 때문에,

최대 작업시간으로 갱신해야 선행 관계에 있는 작업을 모두 완료한 상태인 것을 알 수 있다.

 

마찬가지로 결과값을 출력 할때도 result배열의 최대값을 출력해줘야 정답이다.