[BOJ] 1005 ACM Craft

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

 위상 정렬의 대표격인 건설 순서 문제이다. 그런데 사실 난이도가 아주 없는 문제는 아니어서 이게 왜 1005번에 있나 조금 의심이 들기는 하는 부분이다. 사실 습격자 초라기에 비할 바는 못되지만...

 하여튼 내 풀이를 설명하자면, DFS를 이용해 그래프를 순회하면서 함수가 종료할 때마다 저장하면 위상 정렬의 역순이 된다는 점을 이용해서 DP를 돌리는 방법으로 문제를 풀었다. 이를 위해서 순방향 간선과 역방향 간선의 인접 리스트를 별도로 만들었고, 역방향 간선의 인접 리스트의 크기가 0인 것들을 모두 DFS 돌리고 reverse해서 위상 정렬을 찾은 다음 그걸 역방향 간선 인접 리스트를 통해 바텀업 DP로 돌려서 결과값을 찾아냈다.

 그런데 다른 블로그를 뒤적거려 보니까 그냥 탑다운으로 DFS를 돌리면서 다이나미컬 백트래킹으로 구현하는 편이 훨씬 나았을 것 같다. 하여튼 그건 기회 되면 짜 보기로 하고 일단은 위상 정렬을 찾는 것과 바텀업 DP(라고 하기 뭐한 것)을 연습했다는 것에 의의를 두고 싶다.

 개인적인 감상이지만 내가 짠 코드가 너무 심하게 복잡하고 난해하다. 난이도는 2/5정도 되는 듯.

#include <vector>
#include <cstdio>
#include <algorithm>
 
using namespace std;
 
void dfs(vector<vector<int> > &lis, vector<int> &check, vector<int> &s, int x)
{
    check[x]=1;
    vector<int> &here=lis[x];
    for(int i=0;i<here.size();i++)
    {
        if(check[here[i]]==1) continue;
        dfs(lis,check,s,here[i]);
    }
    s.push_back(x);
}
 
void solve()
{
    int n,m;
    scanf("%d %d",&n,&m);
    vector<int> time(n+1);
    vector<vector<int> > lis(n+1,vector<int>()), ed(n+1,vector<int>());
    vector<int> check(n+1,0), dp(n+1,-1);
    vector<int> s;
    for(int i=1;i<=n;i++)
    {
        int t;
        scanf("%d",&t);
        time[i]=t;
    }
    for(int i=0;i<m;i++)
    {
        int t1,t2;
        scanf("%d %d",&t1,&t2);
        lis[t1].push_back(t2);
        ed[t2].push_back(t1);
    }
 
    for(int i=1;i<=n;i++)
    {
        if(ed[i].size()!=0) continue;
        dfs(lis,check,s,i);
        dp[i]=time[i];
    }
    reverse(s.begin(),s.end());
 
    for(auto it=s.begin();it!=s.end();it++)
    {
        int k=*it;
        if(dp[k]!=-1) continue;
        for(auto jt=ed[k].begin();jt!=ed[k].end();jt++)
            dp[k]=max(dp[k],dp[*jt]);
        dp[k]+=time[k];
    }
 
    int w;
    scanf("%d",&w);
    printf("%d\n",dp[w]);
}
 
int main()
{
    int tc;
    scanf("%d",&tc);
    while(tc--)
        solve();
    return 0;
}