백준 문제 1005번 ACM Craft 문제풀이 c++

https://www.acmicpc.net/problem/1005

1005번: ACM Craft

 

문제설명

 

위상정렬로도 풀 수있고 dfs+dp로 풀 수도 있는 문제인데 저는 후자로 풀었습니다.

 

예제처럼 입력이 들어오면 위 그림과 같이 트리를 만들었고 시작은 4번건물에서 시작을 했습니다.

 

4번에서 dfs를 돌면 4->2->1->3의 순서로 순회를 돌겁니다.

dfs(4)는 dfs(2)를 부르고 dfs(2)는 dfs(1)을 부르고 1이 끝이니 dfs(2)로 리턴 dfs(2)도 dfs(4)로 리턴 그 후 

dfs(4)는 dfs(3)를 부르고 dfs(1)을 부르고 싶지만 이미 방문을 했으므로 종료할겁니다.

 

그리고 방문여부를 ans배열로 확인을 할 것 이고 ans[n]의 정의를 n번 건물을 만드는데 걸리는 시간이라고 정의를합니다.

 

이렇게 정의를 한 후에 4->2->1까지 dfs(4)로 다시 돌아온 후에 ans[4]에는 21 ans[2]에는 11 ans[1]에는 10 값이 들어있을겁니다.

 

그 후 dfs(4)까지 다시 돌아와서 dfs(3)을 호출할 것 이고 dfs(3)은 dfs(1)을 호출 할겁니다.

 

그런데 dfs(1)에서 ans[1]은 이미 값이 10으로 할당이 되어있으므로 그 값 10을 리턴하게하고 그러면 ans[3]에는 100+10=110이 들어갑니다.

dfs(4)에서 기존의 21과 새로운 110+10=120을 비교해서 120이 크므로 ans[4]의값은 21에서 120으로 바뀝니다.

 

이 값을 리턴하면 그것이 답이 됨.

 

단 0 ≤ Di ≤ 100,000라고 문제에 명시가 되어있기 때문에 ans를 처음에 이 범위에 해당하지 않는 -1으로 초기화했음.

 

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
typedef long long int ll;
using namespace std;
void reset();
ll dfs(ll n);
ll ans[1001];
ll delay[1001];
vector <ll> v[1001];
int main(){
    cout.tie(NULL);
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    ll t,n,k,x,y,w;
    cin>>t;
    while(t--)
    {
        reset();
        cin>>n>>k;
        for(ll i=1; i<=n; i++)
        {
            cin>>delay[i];
        }
        for(ll i=1; i<=k; i++)
        {
            cin>>x>>y;
            v[y].push_back(x);
        }
        cin>>w;
        cout<<dfs(w)<<"\n";
    }
}
void reset(){
    for(ll i=0; i<1001; i++)
    {
        ans[i]=-1;
        delay[i]=0;
        v[i].clear();
    }
}
ll dfs(ll n){
    if(v[n].size()==0)
    {
        ans[n]=delay[n];
        return ans[n];
    }
    if(ans[n]!=-1)
    {
        return ans[n];
    }
    else
    {
        for(ll i=0; i<v[n].size(); i++)
        {
            ans[n]=max(ans[n],delay[n]+dfs(v[n][i]));
        }
        return ans[n];
    }
}