백준 1005 ACM Craft (Java)

1. 문제 링크

1005번: ACM Craft

 

2. 문제 및 입출력예제

 

3. 문제 풀이

1. 건설 순서가 우선되는 것이 있어서 위상정렬을 한다.
2. 위상 정렬을 하면서 큐에서 꺼낼 때 dp를 다.
3. dp에 있는 값과 지금 온 값 중 더 큰 시간을 저장하면 문제에서 원하는 결과를 얻을 수 있다.

 

4. 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.io.IOException;

public class Main {
	static class Node{
		int vertex;
		Node link;
		public Node(int vertex, Node link) {
			super();
			this.vertex = vertex;
			this.link = link;
		}
	}
	static int N, K, D[], W, in[], result = 0, dp[];
	static Node[] nodes;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int T = Integer.parseInt(br.readLine());		
		for(int t=0;t<T;t++) {
			String[] split = br.readLine().split(" ");
			N = Integer.parseInt(split[0]);
			K = Integer.parseInt(split[1]);
			nodes = new Node[N+1];
			D = new int[N+1];
			in = new int[N+1];
			dp = new int[N+1];
			split = br.readLine().split(" ");
			for(int i=1;i<N+1;i++) {
				D[i] = Integer.parseInt(split[i-1]);
			}
			int from, to;
			for(int i=0;i<K;i++) {
				split = br.readLine().split(" ");
				from = Integer.parseInt(split[0]);
				to = Integer.parseInt(split[1]);
				nodes[from] = new Node(to, nodes[from]);
				in[to]++;
			}
			W = Integer.parseInt(br.readLine());
			topologySort();
			
			sb.append(dp[W]).append("\n");
		}
		System.out.println(sb);
	}
	
	static void topologySort(){
		Queue<Integer> queue = new ArrayDeque<>();
		for(int i=1;i<N+1;i++) {
			if(in[i] == 0) {
				dp[i] = D[i];
				queue.offer(i);
			}
		}
		
		while(!queue.isEmpty()) {
			int current = queue.poll();
			for(Node temp = nodes[current]; temp!=null; temp = temp.link) {
				int now = temp.vertex;
				dp[now] = Math.max(dp[current]+D[now], dp[now]);
				if(--in[now] == 0) {
					queue.offer(temp.vertex);
				}
			}
		}
	}
}