BOJ 1005번 ACM Craft ( 위상정렬, DP ) JAVA

BOJ 1005번 ACM Craft ( 위상정렬, DP ) JAVA

---

풀이

위상 정렬과 DP를 이용하는 문제입니다.

1005번 문제라, 예전부터 나중에 풀어야지 풀어야지 하다가 이번에 풀게 됐네요..!

난이도가 골드 3이라 되어있는데, 다른 위상 정렬 문제에 비해서 난이도가 낮지는 않은 걸로 생각돼서 이 난이도는

조금 수정이 필요하지 않나 생각됩니다.

 

링크

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

 

소스 코드

---

package boj;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Boj1005 {
    static int T;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        StringBuilder sb = new StringBuilder();
        T = sc.nextInt();
        first:
        while (T-- > 0) {
            int n, k;
            n = sc.nextInt();
            k = sc.nextInt();
            int[] cost = new int[n + 1];
            int[] ans = new int[n + 1];
            int[] parentNum = new int[n + 1];
            ArrayList<ArrayList<Integer>> map = new ArrayList<>();
            Queue<Integer> q = new LinkedList<>();
            for (int i = 0; i <= n; i++) {
                map.add(new ArrayList<>());
            }
            for (int i = 1; i <= n; i++) {
                cost[i] = sc.nextInt();
            }
            for (int i = 0; i < k; i++) {
                int a, b;
                a = sc.nextInt();
                b = sc.nextInt();
                map.get(a).add(b);
                parentNum[b]++;
            }
            int find = sc.nextInt();
            for (int i = 1; i <= n; i++) {
                if (parentNum[i] == 0) {
                    q.add(i);
                    ans[i] = cost[i];
                    if (i == find) {
                        sb.append(ans[i]).append('\n');
                        continue first;
                    }
                }
            }
            while (!q.isEmpty()) {
                int cur = q.poll();
                for (int next : map.get(cur)) {
                    parentNum[next]--;
                    ans[next] = Math.max(ans[next], ans[cur] + cost[next]);
                    if (parentNum[next] == 0) {
                        if (next == find) {
                            sb.append(ans[next]).append('\n');
                            continue first;
                        }
                        q.add(next);
                    }
                }
            }
        }
        System.out.print(sb);

    }
}