[C++][백준 2056] 작업

[문제]

2056번: 작업 (acmicpc.net)

2056번: 작업

[문제 풀이]

위상정렬 알고리즘을 이용하면 바로 풀리는 문제이다.

source로부터 이어지는 숫자들이 저장될  vector<int> graph[n]과 가중치가 저장될 cost[n] 그리고 해당 source로부터 이어진 숫자가 몇개인지 파악할 deg[n] 3가지 요소를 이용하면 바로 풀린다.

자세한 사항은 위상정렬 알고리즘 참조.

[회고]

(2023.04.06) 어디를 고쳐서 해결이 된지 아직 못찾음. 알고리즘 로직 자체의 문제는 아니고 변수를 바꾸다가 해결이 되어서 변수의 문제라고 추측.

[코드]

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

vector<int> adj[10010];
int deg[10010];
int cost[10010];
int cost2[10010];
int n;
int max_answer;

void solve(){

    queue<int> q;
    for(int i = 1;i<=n;i++){
        if(deg[i] == 0){
            q.push(i);
        }
        cost2[i] = cost[i];
    }
    
    while(q.size() > 0){
        int cur = q.front();
        q.pop();
        for(int i = 0;i<adj[cur].size();i++){
            int next = adj[cur][i];
            deg[next]--;
            if(deg[next] == 0){
                q.push(next);
            }
            cost2[next] = max(cost2[next],cost2[cur] + cost[next]);
        }
    }
    return;
}

int main(){
    cin>>n;
    for(int i = 1;i<=n;i++){
        int source = i;
        int price,num;
        cin>>price>>num;
        cost[i] = price;
        for(int j = 0;j<num;j++){
            int temp;
            cin>>temp;
            adj[temp].push_back(i);
            deg[i]++;
        }
    }
    solve();

    for(int i = 1;i<=n;i++){
        max_answer = max(max_answer,cost2[i]);
    }
    cout<<max_answer<<endl;

    return 0;
}