BOJ 1005(ACM Craft)풀이

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

1005번: ACM Craft

dfs를 사용해서 거꾸로 탐색하는 방법을 사용했다.

문제를 보면 자신에게 오는 간선이랑 연결되어있는 점까지의 delay가 가장 큰 값을 골라야 된다. 그러므로 마지막부터 거꾸로 탐색하면서 max값을 저장한 뒤 현재 노드의 값을 더해서 출력해주면 된다.

문제에 있는 그림으로 예시를 들면 4번 노드에서 2,3번 노드로 탐색을 하고 2,3번 노드에서 1번노드로 탐색을 한다. 1번 노드에서는 갈 수 있는 노드가 없으므로 1번 노드의 delay값을 return 하고 2,3번 노드도 자신의 delay와 값을 더해 return 한다. 마지막으로 4번 노드에서 둘 중 큰 값을 고르고 4번 노드의 delay를 더해서 return 해주면 끝이다.

 

 

 

import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**9)
n=int(input())
def f(x):
    m=0
    for next in graph[x]:
        if st[next]==-1:
            m=max(m,f(next))
        else:
            m=max(m,st[next])
    st[x]=m+l[x-1]
    return st[x]
for _ in range(n):
    a,b=map(int,input().split())
    l=list(map(int,input().split()))
    graph=[[]for i in range(a+1)]
    for i in range(b):
        c,d=map(int,input().split())
        graph[d].append(c)
    st=[-1]*(a+1)
    c=int(input())
    print(f(c))
    #print(st)