[1516] 게임 개발

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

public class Main {
	static int N, dp[];
	static List<Node>[] list;
	static Queue<Node> q;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		N = Integer.parseInt(br.readLine());
		list = new ArrayList[N+1];
		dp = new int[N+1];
		q = new LinkedList<>();
		
		for(int i=0; i<=N; i++) {
			list[i] = new ArrayList<>();
		}
		
		
		for(int i=1; i<=N; i++) {
			st = new StringTokenizer(br.readLine());
			int time = Integer.parseInt(st.nextToken());
			int check =0;
			int from = 0; 
			while((from=Integer.parseInt(st.nextToken())) != -1) {
				check++;
				list[from].add(new Node(i,time));
			}
			if(check==0) {
				q.add(new Node(i,time));
				dp[i] = time;
			}
		}
		
		fn();
		
		for(int i=1; i<=N; i++) {
			System.out.println(dp[i]);
		}
		
	}

	public static void fn() {
		
		while(!q.isEmpty()) {
			Node node = q.poll();
			int from = node.to;
			int time = node.time;
			
			for(int i=0; i<list[from].size(); i++){
				Node n = list[from].get(i);
				dp[n.to] = Math.max(dp[n.to], time+n.time);
				q.offer(new Node(n.to,dp[n.to]));
			}
			
		}
		
	}
	
	public static class Node{
		int to;
		int time;
		
		public Node(int to, int time) {
			super();
			this.to = to;
			this.time = time;
		}
		
	}
	
}

시간초과

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

public class Main {
	static int N, dp[];
	static List<Node>[] list;
	static Queue<Node> q;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		N = Integer.parseInt(br.readLine());
		list = new ArrayList[N+1];
		dp = new int[N+1];
		q = new LinkedList<>();
		
		for(int i=0; i<=N; i++) {
			list[i] = new ArrayList<>();
		}
		
		
		for(int i=1; i<=N; i++) {
			st = new StringTokenizer(br.readLine());
			int time = Integer.parseInt(st.nextToken());
			int check =0;
			int from = 0; 
			while((from=Integer.parseInt(st.nextToken())) != -1) {
				check++;
				list[from].add(new Node(i,time));
			}
			if(check==0) {
				q.add(new Node(i,time));
				dp[i] = time;
			}
		}
		
		fn();
		
		for(int i=1; i<=N; i++) {
			System.out.println(dp[i]);
		}
		
	}

	public static void fn() {
		
		while(!q.isEmpty()) {
			Node node = q.poll();
			int from = node.to;
			
			for(int i=0; i<list[from].size(); i++){
				Node n = list[from].get(i);
				if(dp[n.to]<dp[from]+n.time) {
					dp[n.to] = dp[from]+n.time;
					q.offer(new Node(n.to,dp[n.to]));
				}
			}
			
		}
		
	}
	
	public static class Node{
		int to;
		int time;
		
		public Node(int to, int time) {
			super();
			this.to = to;
			this.time = time;
		}
		
	}
	
}

통과 시간 : 400ms

다른사람풀이

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

public class Main {
	static int N;
	static int[] build_time;
	static int[] before_time;
	static int[] degree_cnt;
	static Queue<Integer> job_queue = new LinkedList<>();
	static ArrayList<Integer>[] in_degree;
	static StringBuilder str = new StringBuilder();
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		N = Integer.parseInt(br.readLine());
		build_time = new int[N+1];
		before_time = new int[N+1];
		degree_cnt = new int[N+1];
		in_degree = new ArrayList[N+1];
		for (int i = 1; i <= N; i++) {
			in_degree[i] = new ArrayList<>();
		}

		for (int i = 1; i <= N; i++) {
			st = new StringTokenizer(br.readLine());
			int t = Integer.parseInt(st.nextToken());
			build_time[i] = t;
			int need_build;
			while ((need_build = Integer.parseInt(st.nextToken())) != -1){
				in_degree[need_build].add(i);
				degree_cnt[i]++;
			}
		}

		for (int i = 1; i < N+1; i++) {
			if (degree_cnt[i] == 0) {
				job_queue.add(i);
				before_time[i] = build_time[i];
			}
		}

		while (!job_queue.isEmpty())
		{
			int now = job_queue.poll();

			for (int next_build : in_degree[now])
			{
				//degree_cnt : next_build를 건설하기 위해 필요한 선행 건물 수 
				degree_cnt[next_build]--;
				if (before_time[next_build] < before_time[now] + build_time[next_build])
					before_time[next_build] = before_time[now] + build_time[next_build];
				
				//만약 선행 건물수가 0이면 설치가 가능해 지니 q에 추가 한다.
				if (degree_cnt[next_build] == 0) {
					job_queue.add(next_build);
				}
			}
		}

		for (int i = 1; i < N + 1; i++) {
			str.append(before_time[i]).append("\n");
		}
		System.out.print(str);
	}
}