2056번

2056번 - 작업

위상정렬을 이용한 문제풀이다. 위상정렬은 2가지 풀이방식이 있는데, 그 중에서 BFS로 풀었다.

indegree 값을 구하고, dist[i] 배열에는 i번 작업이 끝나는 시간으로 정의했다.

(처음에 dist[i]=i번 작업이 시작하는 시간으로 정의했는데, 그럴 경우 맨 마지막에 호출되는, out-degree 가 0인 작업들은

다시 한번 계산해줘야 하는 번거로움이 있었다.)

또 처음에 while 문 안에서 queue 가 empty 가 될 때, dist 값을 구했는데, 그러면 안됐다. 마찬가지로 out-degree 가 0인 작업들 중에서

시간이 최대로 많이 걸리는 애가 선택이 되는게 아니기 때문이다.

<정답 코드>

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
 
vector<int> v[10001];
int t[10001];
int indegree[10001];
int dist[10001];
int main()
{
    int N;
    scanf("%d", &N);
 
    for (int i = 1; i <= N; i++)
    {
        scanf("%d", &t[i]);
        int m;
        scanf("%d", &m);
        for (int j = 0; j < m; j++)
        {
            int a;
            scanf("%d", &a);
            v[a].push_back(i);
            indegree[i]++;
        }
    }
 
    queue<int> q;
 
    for (int i = 1; i <= N; i++)
    {
        if (indegree[i] == 0)
        {
            q.push(i);
            dist[i] = t[i];
        }
    }
 
    while (!q.empty())
    {
        int now = q.front();
        q.pop();
 
        for (int i = 0; i < v[now].size(); i++)
        {
            int next = v[now][i];
            indegree[next]--;
 
            dist[next] = max(dist[next], dist[now] + t[next]);
 
            if (indegree[next] == 0)
            {
                q.push(next);
            }
        }
    }
 
    int ans = 0;
    for (int i = 1; i <= N; i++)
    {
        if (ans < dist[i])
        {
            ans = dist[i];
        }
    }
 
    printf("%d\n", ans);
 
    return 0;
}