ACM Craft C++ - 백준 1005

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

이 문제는 위상 정렬을 배우고 풀었다.

먼저 위상 정렬 없이 시도해본 결과 메모리 초과가 났다.

벡터는 문제가 없는데, 아마 큐에 엄청나게 많이 담겨 메모리 초과가 난 것으로

예상이 되었다.

따라서 위상 정렬 + dp를 채택해 코드를 작성했다.

먼저 입력 받을 때 선행되어야 하는 노드들을 모아놓는 벡터,

진입차수 배열에 입력을 받아주고,

매번 진입차수가 0인 노드들을 큐에 넣어 bfs + dp를 돌려주었다.

코드는 다음과 같다.

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

int t;

void solve(){
    int n,k;
    vector<int> v[1001]; //next vector
    vector<int> h[1001]; //req vector
    int reqarr[1001];
    memset(reqarr,0,sizeof(reqarr));
    int dp[1001];
    int arr[1001];
    int tmp[2];
    int target;
    queue<int> q;
    cin >> n >> k;
    for(int i=1;i<=n;i++) cin >> arr[i];
    for(int i=0;i<k;i++){
        cin >> tmp[0] >> tmp[1];
        v[tmp[0]].push_back(tmp[1]);
        h[tmp[1]].push_back(tmp[0]);
        reqarr[tmp[1]]++;
    }
    cin >> target;
    for(int i=1;i<=n;i++){if(reqarr[i]==0) q.push(i);}
    while(!q.empty()){
        int x=q.front();
        q.pop();
        dp[x]=arr[x];
        int maxi=0;
        for(int i=0;i<h[x].size();i++) maxi=max(maxi,dp[h[x][i]]);
        dp[x]+=maxi;
        for(int i=0;i<v[x].size();i++){
            reqarr[v[x][i]]--;
            if(reqarr[v[x][i]]==0) q.push(v[x][i]);
        }
    }
    cout << dp[target] << '\n';
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    cin >> t;
    while(t--) solve();
}