작업 C++ - 백준 2056

https://www.acmicpc.net/problem/2056

위상정렬 문제.

문제 접근

다른 위상정렬과 같이 1번 작업부터 N번 작업까지

위상정렬 알고리즘을 수행해주면 된다.

여태까지 위상정렬 알고리즘 문제를 풀 때에는 필요한 노드들을 기록하는

벡터를 사용했었는데, 생각해보니

그 전 노드에서 진입 노드가 최댓값으로만 갱신되도록 하면

필요한 노드를 기록할 필요가 없었다.

따라서 수행시간도 더 빨라졌다.

코드는 다음과 같다.

(전 코드)

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

int n,t[10001],d[10001]={0,},ans=0,inn,cnt[10001];
queue<int> q;
vector<int> nxt[10001],req[10001];

void solve(){
    while(!q.empty()){
        int now=q.front();
        q.pop();
        if(req[now].size()==0) d[now]=t[now];
        else{for(int i=0;i<req[now].size();i++){
                    d[now]=max(d[now],d[req[now][i]]);
                }
            d[now]+=t[now];
        }
        for(int i=0;i<nxt[now].size();i++){
            cnt[nxt[now][i]]--;
            if(cnt[nxt[now][i]]==0) q.push(nxt[now][i]);
        }
        ans=max(ans,d[now]);
    }
    cout << ans;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> n;
    for(int i=1;i<=n;i++){
        cin >> t[i] >> cnt[i];
        if(cnt[i]==0) q.push(i);
        for(int j=0;j<cnt[i];j++){
            cin >> inn; req[i].push_back(inn);
            nxt[inn].push_back(i);
        }
    }
    solve();
    return 0;
}

(수정한 코드)

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

int n,t[10001],d[10001]={0,},ans=0,inn,cnt[10001];
queue<int> q;
vector<int> nxt[10001];

void solve(){
    while(!q.empty()){
        int now=q.front();
        q.pop();
        for(int i=0;i<nxt[now].size();i++){
            cnt[nxt[now][i]]--;
            d[nxt[now][i]]=max(d[nxt[now][i]],d[now]+t[nxt[now][i]]);
            if(cnt[nxt[now][i]]==0) q.push(nxt[now][i]);
        }
        ans=max(ans,d[now]);
    }
    cout << ans;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> n;
    for(int i=1;i<=n;i++){
        cin >> t[i] >> cnt[i];
        if(cnt[i]==0){q.push(i); d[i]=t[i];}
        for(int j=0;j<cnt[i];j++){
            cin >> inn;
            nxt[inn].push_back(i);
        }
    }
    solve();
    return 0;
}