(BOJ) 1516 풀이

#include<bits/stdc++.h>

using namespace std;

vector<int> v[501];
queue<int> q;
int N,times[501],dp[501],in_deg[501],ans[501];
int main(void){
    ios::sync_with_stdio(0);cin.tie(0);
    int a;
    cin >> N;
    for(int i=1;i<=N;i++){
        cin >> times[i];
        cin >> a;
        while(a!=-1){
            v[a].push_back(i);
            in_deg[i]++;
            cin >> a;
        }
    }
    for(int i=1;i<=N;i++){
        if(in_deg[i]==0)q.push(i);
        ans[i]=times[i];
    }
    while(!q.empty()){
        int t=q.front();
        q.pop();
        for(auto i:v[t]){
            ans[i]=max(ans[i],times[i]+ans[t]);
            if(--in_deg[i]==0)
                q.push(i);
        }
    }
    for(int i=1;i<=N;i++){
        cout << ans[i] << '\\n';
    }
}

위상정렬 + DP 문제였다.

---

풀이.

입력받을 때 먼저 지어져야할 건물의 index 에 건물번호를 연결해야한다.

ex : i : 4, 4 3 1 -1

위와 같은 경우에는 건물 3,1 이 먼저 지어져야 하기 떄문에

vector[3], vector[1] 에 건물번호인 4를 연결한다.

이렇게 간선을 연결하고 나면, 위상정렬 순서는 진입차수가 0인 건물 1부터

1 -> 2 -> 3 -> 5 -> 4

위 순서로 진행될 것이다.

걸린 시간은 각각 자신의 건물을 짓는데 걸리는 시간으로 초기화되어있다.

1에는 2,3,4 가 연결되어있고,

3에는 4,5 가 연결되어있다.

1부터 진입을 하면 2,3,4 에는 1을 짓는데 걸리는 걸리는 시간이 더해진다.

그 다음 3에서 4,5 에 3의 지금까지 걸린시간을 더해햐하는데,

4에는 이미 1의 걸린시간이 더해져 있기 때문에

1 걸린시간 + 4 걸리는 시간, 1 걸린시간 + 3 걸린시간 + 4 걸리는 시간

위 둘 중에서 더 큰값을 선택해야한다.

더 큰값을 선택하는 이유는 DP 알고리즘과 관련이 있는데,

값을 계속 갱신해야하기 때문이다.

DP 배운지 오래돼서 까먹었기 때문에 대충 예시를 들어보면,

1 -> 10분 걸림
2 -> 20분 걸림
3 -> 30분 걸림
4 -> 10분 걸리고 1,2,3 먼저 지어야함.

위와 같은 상황에서, 문제조건에는 건물이 동시에 지어질 수 있다고 했기 때문에

1,2,3 건물을 동시에 짓는다고 하면, 30분 걸리는 건물 3을 다 지었을 때 건물 4 를 지을 수 있게 된다.

so, 건물3 시간 + 건물4 시간인 40분이 올바른 답이 된다.

4
10 -1
20 -1
30 -1
10 1 2 3 -1
10, vs ,20
20, vs ,30
30, vs ,40
10
20
30
40

위 예시를 디버깅하면서 출력했을 때 결과다. ans[i] 와 times[i]+ans[t] 을 비교하면서 출력하고있다.