[백준 BOJ] 1005번 - ACM Craft (C++)

1005번: ACM Craft (acmicpc.net)

1005번: ACM Craft

 

전의 것이 모두 건설이 되어야 하므로 메모이제이션 방법을 사용하여 Y->X 순으로 재귀를 돌리면 충분히 해결될 거라 생각했다.

 

#include <iostream>
#include <vector>
#include <cmath>
#include <queue>
#include <memory.h>

#define pii pair<int,int>
#define endl "\n"
#define inf 987654321

using namespace std;

int T,N,K;
int D[1001];
vector<int> edge[1001];
bool check[1001];
int W;

int memo(int x)
{
	if(edge[x].empty())
		return D[x];
	else if(check[x])
		return D[x];
	else
	{
		check[x]=true;
		int max = 0;
		for(int i = 0; i<edge[x].size(); i++)
		{
			int tmp = memo(edge[x][i]);
			if(max<tmp)
				max = tmp;
		}
		D[x]+=max;
		return D[x];
	}
}

int main()
{
	cin>>T;
	while(T--)
	{
		cin>>N>>K;
		for(int i =1; i<=N; i++)
		{
			cin>>D[i];
		}
		int X,Y;
		for(int i = 0; i<K; i++)
		{
			cin>>X>>Y;
			edge[Y].push_back(X);
		}
		cin>>W;
		memo(W);
		cout<<D[W]<<endl;
		memset(check, false, sizeof(check));
		for(int i = 1; i<=N; i++)
			edge[i].clear();
	}
	return 0;
}