[백준]1005. ACM Craft (java, python)

링크

ACM Craft

문제 분석

풀이 1(java)

• bfs의 시작점이 될 루트 노드들을 찾아서 큐에 넣습니다
• BFS를 진행하며 노드들을 방문하며 가장 오래 걸린 시간을 저장합니다

풀이 2(python)

• 풀이 1과는 반대로 목표 지점에서 시작합니다
• 간선 연결을 반대로 연결해줍니다

DP(cur) = MAX(DP(prev)) + time[cur]

• DP를 이용하여 해결합니다

코드

JAVA

import java.io.*;
import java.util.*;

public class Q1005 {
    static int stoi(String s) { return Integer.parseInt(s); };
    static int N, K, ret, e;
    static int[] time, visit;
    static ArrayList<Integer>[] adj;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int tc = stoi(br.readLine());
        while(tc-- > 0) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            N = stoi(st.nextToken()); K = stoi(st.nextToken());
            ret = 0;
            time = new int[N]; visit = new int[N];
            boolean[] root = new boolean[N];
            adj = new ArrayList[N];
            for(int i = 0; i < N; i++)
                adj[i] = new ArrayList<>(N);
            st = new StringTokenizer(br.readLine());
            for(int i = 0; i < N; i++) {
                time[i] = stoi(st.nextToken());
                visit[i] = time[i];
            }
            for(int i = 0; i < K; i++) {
                st = new StringTokenizer(br.readLine());
                int from = stoi(st.nextToken()) - 1, to = stoi(st.nextToken()) - 1;
                adj[from].add(to);
                root[to] = true;
            }
            e = stoi(br.readLine()) - 1;
            Queue<Integer> q = new LinkedList<>();
            for(int i = 0; i < N; i++)
                if(!root[i]) q.add(i);
            while(!q.isEmpty()) {
                int cur = q.poll();
                for(int next : adj[cur]) {
                    if(visit[next] >= visit[cur] + time[next]) continue;
                    visit[next] = visit[cur] + time[next];
                    q.add(next);
                }
            }
            System.out.println(visit[e]);
        }
    }
}

PYTHON

import sys

read = sys.stdin.readline

def dp(w):
    if cache[w] != -1:
        return cache[w]
    if not Ord[w]:
        return time[w]

    ret = 0
    for prev in Ord[w]:
        ret = max(ret, dp(prev) + time[w])
    cache[w] = ret
    return ret


for _ in range(int(read())):
    n, k = map(int, read().split())
    time = [0] + list(map(int, read().split()))
    Ord = [[] for x in range(n + 1)]
    for i in range(k):
        x, y = map(int, read().split())
        Ord[y] += [x]
    W = int(read())
    cache = [-1] * (n + 1)
    print(dp(W))