[BaekJoon] 1005 ACM Craft (Java)

1.  문제 링크

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

2.  문제

요약

• ACM Craft는 다이나믹한 게임 진행을 위해 건물을 짓는 순서가 정해져 있지 않습니다.
• 즉, 첫 번째 게임과 두 번째 게임이 건물을 짓는 순서가 다를 수도 있습니다.
• 매 게임시작 시 건물을 짓는 순서가 주어지고 모든 건물은 각각 건설을 시작하여 완성이 될 때까지 Delay가 존재합니다.
• 특정 건물을 가장 빨리 지을 때까지 걸리는 최소 시간을 알아내는 문제입니다.
• 입력: 첫 번째 줄에 테스트 케이스의 개수 T가 주어지고 두 번째 줄부터 각 테스트 케이스가 주어집니다. 각 테스트 케이스의 첫 번째 줄에 2보다 크거나 같고 1000보다 작거나 같은 건물의 개수 N과 1보다 크거나 같고 100,000보다 작거나 같은 건물간의 건설 순서 규칙의 총 개수 K가 주어지고 두 번째 줄에 0보다 크거나 같고 100,000보다 작거나 같은 각 건물당 건설에 걸리는 시간 $D_1$, $D_2$, ..., $D_N$이 주어집니다. 또한 세 번째 줄부터 K개의 줄에는 1보다 크거나 같고 N보다 작거나 같은 건설 순서 X Y가 주어지고 마지막 줄에는 승리하기 위해 건설해야 할 건물의 번호 W가 주어집니다.
  • 건물의 번호는 1번부터 N번까지 존재합니다.
  • X Y의 의미는 건물 X를 지은 다음 건물 Y를 짓는 것이 가능하다는 의미입니다.
• 출력: 건물 W를 건설완료 하는데에 드는 최소 시간을 출력합니다.
  • 건물을 짓는 명령을 내리는 데는 시간이 소요되지 않는다고 가정하고 건설순서는 모든 건물이 건설 가능하도록 주어집니다.

3.  소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	static StringBuilder sb = new StringBuilder();
	static int N, K, W;
	static int[] time, linkNum;
	static HashMap<Integer, ArrayList<Integer>> map;
	static void input() {
		Reader scanner = new Reader();
		int T = scanner.nextInt();
		for(int test = 0; test < T; test++) {
			N = scanner.nextInt();
			K = scanner.nextInt();
			time = new int[N + 1];
			linkNum = new int[N + 1];
			map = new HashMap<Integer, ArrayList<Integer>>();
			for(int structure = 1; structure <= N; structure++) map.put(structure, new ArrayList<Integer>());
			for(int structure = 1; structure <= N; structure++) time[structure] = scanner.nextInt();
			for(int link = 0; link < K; link++) {
				int first = scanner.nextInt();
				int second = scanner.nextInt();
				map.get(first).add(second);
				linkNum[second]++;
			}
			W = scanner.nextInt();
			solution();
		}
	}
	
	static void solution() {
		Queue<Integer> structures = new LinkedList<Integer>();
		int[] answer = new int[N + 1];
		for(int structure = 1; structure <= N; structure++) {
			if(linkNum[structure] == 0) {
				answer[structure] = time[structure];
				structures.offer(structure);
			}
		}
		while(!structures.isEmpty()) {
			int curStructure = structures.poll();
			for(int structure : map.get(curStructure)) {
				answer[structure] = Math.max(answer[structure], answer[curStructure] + time[structure]);
				linkNum[structure]--;
				if(linkNum[structure] == 0) structures.offer(structure);
			}
		}
		sb.append(answer[W]).append('\n');
	}
	
	public static void main(String[] args) {
		input();
		System.out.println(sb.toString());
	}
	
	static class Reader {
		BufferedReader br;
		StringTokenizer st;
		public Reader() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}
		String next() {
			while(st == null || !st.hasMoreElements()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch(IOException e) {
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}
		int nextInt() {
			return Integer.parseInt(next());
		}
	}
}