문제

문제 링크

문제 접근

  • 이 문제는 건물을 짓는데 의존성이 있다는 이야기를 보고 바로 위상 정렬을 떠올렸다.
  • 인풋을 받을 때 incoming edge의 수를 기억하도록 하고 의존성에 대한 edge를 저장해서 하나씩 꺼내보도록 하였다.
  • 다음을 n번 반복한다.
  • incoming edge의 수가 0이 되면 그 건물이 지을 수 있을 때 이므로 처음부터 이런 친구를 찾아 짓는데 필요한 시간을 추가하고
  • 자식 노드로 뻗쳐나가 자기를 짓는데 필요한 시간을 전달해서 현재 자식 노드가 지어지기 전 시간보다 크면 이를 대체한다.
  • 그리고 incoming edge의 수를 하나 줄여준다.

코드

#include <cstdio>
#include <vector>
using namespace std;
char buf[1 << 17];

inline char read() {
    static int idx = 1 << 17;
    if (idx == 1 << 17) {
        fread(buf, 1, 1 << 17, stdin);
        idx = 0;
    }
    return buf[idx++];
}
inline int readInt() {
    int sum = 0;
    bool flg = 1;
    char now = read();

    while (now == 10 || now == 32) now = read();
    if (now == '-') flg = 0, now = read();
    while (now >= 48 && now <= 57) {
        sum = sum * 10 + now - 48;
        now = read();
    }

    return flg ? sum : -sum;
}
int t, n, in[501], w[501], ans[501];
vector<vector<int> > e;
int main(){
    n = readInt();
    e = vector<vector<int> >(n+1);
    for(int i = 1; i <= n; i++){
        w[i] = readInt();
        while(1){
            t = readInt();
            if(t == -1)break;
            e[t].push_back(i);
            in[i]++;
        }
    }
    for(int i = 0; i < n; i++){
        for(int j = 1; j <= n; j++){
            if(in[j])continue;
            in[j] = 1;
            ans[j] += w[j];
            for(int k = 0; k < e[j].size(); k++){
                int next = e[j][k];
                in[next] --;
                if(ans[next] < ans[j])ans[next] = ans[j];
            }
            break;
        }
    }
    for(int i = 1; i <= n; i++)printf("%d\n", ans[i]);
}

느낀점

  • 이 알고리즘을 떠올리고 10분만에 구현해냈다.
  • 빠르게 실수없이 알고리즘을 완성해낼 수 있어서 좋았다!