[알고리즘] 1516번

오늘 풀어볼 문제는 백준 1516번 문제이다.

📌 도전 📌
앞에서 푼 2252번하고 비슷하게 문제를 풀었다. 약간 추가된 점은 시간을 추가했다는 점이다.

ans[next] = Math.max(ans[next], ans[now] + time[now]);

이 코드를 추가하여 최대인 값을 넣는 것이다.

public class Main {
    static int n;
    static ArrayList<ArrayList<Integer>> arr;
    static int[] count;
    static int[] time;
    static int[] ans;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        arr = new ArrayList<>();
        for(int i=0; i <= n; i++) {
            arr.add(new ArrayList<>());
        }
        count = new int[n+1];
        time = new int[n+1];
        ans = new int[n+1];

        for(int i=1; i <= n; i++) {
            st = new StringTokenizer(br.readLine());
            time[i] = Integer.parseInt(st.nextToken());
            while (true) {
                int e = Integer.parseInt(st.nextToken());
                if(e == -1) {
                    break;
                }
                arr.get(e).add(i);
                count[i]++;
            }
        }

        Queue<Integer> queue = new LinkedList<>();
        for(int i=1; i<=n; i++) {
            if(count[i] == 0) {
                queue.offer(i);
            }
        }

        while (!queue.isEmpty()) {
            int now = queue.poll();
            for(int next : arr.get(now)) {
                count[next]--;
                ans[next] = Math.max(ans[next], ans[now] + time[now]);
                if(count[next] == 0) {
                    queue.offer(next);
                }
            }
        }

        for(int i=1; i<=n; i++) {
            System.out.println(ans[i] + time[i]);
        }
    }
}

[문제 출처] : https://www.acmicpc.net/problem/1516