BOJ - 1005 ACM Craft

1005번 ACM Craft

특정 건물을 짓기 위해 앞서 지어져야 할 건물들이 존재한다. 이전에 지어져야 할 건물들은 동시에 지어질 수 있으며, 걸리는 시간이 0일 수 있다.

문제 해결 전략

예를 들어 3번 건물을 짓기 위해 1번과 2번 건물을 지여야 한다고 하자.

3번 건물을 짓는 시간은 건물이 동시에 지어질 수 있기 때문에 1번과 2번 건물 중
더 오래 걸리는 건물의 시간 + 3번 건물 짓는 시간 이 된다.

4번 건물을 짓기 위해 3번과 1번 건물을 지어야 한다고 하면, 3번을 건설하는 과정에서 1번을 건설하기 때문에 남은 1번 건물에 대해서는 생각하지 않아도 된다.

즉, 건물을 지을 때 이미 지어진 건물에 대해서는 생각하지 않아도 된다.

위의 내용을 정리해 보자면 지을 건물에 대해 dfs를 적용 하는데, 이미 지어진 건물이라면 그 건물이 지어지는 데 걸리는 시간과 아직 지어지지 않은 건물이라면 해당 건물에 대해 dfs를 적용한 시간 을 비교하여 가장 큰 시간을 반환하면 된다.

dfs 과정에서 이미 지어진 건물에 대한 시간을 유지하여야 하기 때문에 dp를 사용한다.

코드

#include <iostream>
#include <vector>
using namespace std;

int visited[1001];
int rec(int a, vector<int> v, vector<int> *g){
    if(g[a].size() == 0)
    {
        visited[a] = v[a];
        return v[a];
    }

    int max = 0;
    for(int i=0;i<g[a].size();i++)
    {
        int tmp;
        if(visited[g[a][i]] != -1)
            tmp = visited[g[a][i]];
        else
            tmp = rec(g[a][i], v, g);

        if(max < tmp)
            max = tmp;
    }
    visited[a] = max + v[a];
    return max + v[a];
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int t;
    cin >> t;

    for(int test=0;test<t;test++)
    {
        int n,k,m;
        cin >> n >> k;
        vector<int> v(n+1);
        for(int i=1;i<=n;i++)
            cin >> v[i];

        for(int i=0;i<=n;i++)
            visited[i] = -1;

        vector<int> *g = new vector<int>[n+1];
        for(int i=0;i<k;i++)
        {
            int s,e;
            cin >> s >> e;
            g[e].push_back(s);
        }

        cin >> m;

        int max = 0;
        for(int i=0;i<g[m].size();i++)
        {
            int tmp = rec(g[m][i], v, g);
            if(max < tmp)
                max = tmp;
        }

        cout << max + v[m] << "\n";
    }
    return 0;
}

생각해 볼 점
위상정렬 : https://gmlwjd9405.github.io/2018/08/27/algorithm-topological-sort.html

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