[백준 1005] ACM Craft [C]

백준 - 1005

---

풀이

건물 W를 완성하기 위해서는 건물 1에서 건물 W로 향하는 건물들이 완성되어야 하기 때문에, W값에서 역으로 DFS방식을 사용했다.

W에서 1로 향하는 건물들이 모두 건설되어야 하기 때문에 D값이 가장 큰 값을 time에 넣어주어 반환해야 한다.

 

좀더 효율적인 탐색을 위해 총 time을 check에 넣는 memoization방식으로 해결했다.

단, D값은 0이상이기 때문에 -1로 초기화해서 사용해야 한다.

---

소스코드

#include <stdio.h>
#include <stdbool.h>
#include <memory.h>
#define max(a, b) a > b ? a : b
int D[1001], N, check[1001];
bool O[1001][1001];
int construction(int c){
    if (check[c] != -1) return check[c];
    int time = 0;
    for (int i = 1; i <= N; i++)
        if (O[i][c])
            time = max(time, construction(i));
    return check[c] = time + D[c];
} 
int main(){
    int T;
    scanf("%d", &T);
    while (T--){
        memset(D, 0, sizeof(D));
        memset(O, false, sizeof(O));
        memset(check, -1, sizeof(check));
		
        int K, W;
        scanf("%d %d", &N, &K);
        for (int i = 1; i <= N; i++)
            scanf("%d", &D[i]);
        for (int i = 0, o1, o2; i < K; i++){
            scanf("%d %d", &o1, &o2);
            O[o1][o2] = true;
        }
        scanf("%d", &W);
        printf("%d\n", construction(W));
    }
}

---

출처

1005번: ACM Craft