백준 1005번 문제 - ACMCRAFT

---

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

1005번 문제는 특정 건물을 건설하는데 있어 건설해야할 건물이 존재한다는 점, 동시 건설이 가능하다는 점에 주목하여 문제를 풀어야 한다.

특히 동시 건설의 경우 오래 걸리는 시간에 의해 전체 건설 시간이 결정되므로 임의의 건물이 필요로한 건물들을 건설하는 데 걸리는 시간들 중 최대 값을 기준으로 계산하여 구현해야 한다.

특정 건물을 건설하기 위해서는 요구되는 건물들을 모두 건설하여야 하므로 최소시간은 중복 건설이 일어나지 않는다면 요구되는 건물들의 동시 건설에 의하여 찾을 수 있다.

//1005
#include<iostream>
#include<vector>
using namespace std;
#define MAXSIZE 1001
int D[MAXSIZE]={0};//건물 건설 시간
vector<int> required[MAXSIZE]; //요구되는 건물 리스트
int time[MAXSIZE]={0};//동적 계획법을 이용하여 반복되는 계산을 방지
int T,N,K;//테스트케이스 T, 건물 수 N, 건물 순서 규칙 수 K

int build(int w){
	if(time[w]!=-1) return time[w]; //미리 계산된 건설시간이 있다면 시간을 절약할 수 있음
	if(required[w].empty()) return time[w] = D[w];  //요구 건물이 없을 경우 건설
	int max=0, calculated=0;
	for(int i=0;i<required[w].size();i++){  //건물 w를 건설하기 위해 필요한 건물 리스트업
		calculated = build(required[w][i]); //임의의 요구 건물을 건설하는데 걸리는 시간 계산
		if(calculated>max) max = calculated;  //동시 건설시 결정되는 시간
	}
	return time[w] = max + D[w]; //요구 건물의 동시건설시간 + 건물 W의 건설시간 = 전체 건설시간
}

int main(){
	int X,Y;
	scanf("%d",&T);
	while(T--){
        scanf("%d %d",&N,&K);
		for(int i=1;i<=N;i++){//각 테스트케이스마다 초기화 필요
			required[i].clear();
            time[i]=-1;
			scanf("%d",&D[i]);//건물 건설 시간 D
		}
		while(K--){
			//건물 건설 순서 규칙
			scanf("%d %d",&X,&Y);
			required[Y].push_back(X);
		}
		//목표 건물 W
		int W;
		scanf("%d",&W);
		printf("%d\n",build(W));
    }	
	return 0;
}