BOJ - 1005 ) ACM Craft

 

---

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

1005번: ACM Craft

 

---

위상정렬과 다이나믹프로그래밍(약간?)이 결합된 문제이다. 

 

빌드와 시간이라는 개념이 등장하여 1 ->2 ->3 , 11->10->3 의 노드 연결정보에서

 

3의 진입차수가 0 이될때 1->2 / 11->10의 비용중 큰것을 골라야지 다른 빌드에서 걸리는 시간을 커버하면서 

 

진행 할 수 있다. 중간중간 첫 건물이 목표건물인 경우와같이 예외사항을 처리해주면서 진행하면 풀리는 문제..

 

위상정렬을 DFS로 구현했었는데 이문제도 도전해봐야겠다.

 

 

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class ACMCraft {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		StringBuilder sb = new StringBuilder();
		int T = Integer.parseInt(st.nextToken());
		ArrayDeque<Integer> dq = new ArrayDeque<>();
		for(int tc=0 ; tc< T ;tc++) {
			st = new StringTokenizer(br.readLine());
			int n = Integer.parseInt(st.nextToken());
			int k = Integer.parseInt(st.nextToken());
			int degree[] = new int[n];
			int buildtime[] = new int[n];
			int time[] = new int[n];
			st = new StringTokenizer(br.readLine());
			for(int i = 0 ; i < n ; i++) {
				buildtime[i] = Integer.parseInt(st.nextToken());
			} // 건설시간 저장 배열
			ArrayList<Integer> node[] = new ArrayList[n];
			for(int i = 0 ; i < n ; i ++) node[i] = new ArrayList<>();
			for(int i = 0 ; i < k ; i ++) {
				st = new StringTokenizer(br.readLine());
				int from = Integer.parseInt(st.nextToken()) -1;
				int to = Integer.parseInt(st.nextToken()) -1;
				node[from].add(to);
				degree[to]++;
				// 차수저장배열
			}
			st = new StringTokenizer(br.readLine());
			int target = Integer.parseInt(st.nextToken()); 
					
			int max = -1;
			boolean isContinue = true;
			for(int i = 0 ; i < n ; i++) {
				if(degree[i] ==0) {
					time[i] = buildtime[i];
					if(target-1 ==i) {
						isContinue = false;
						break;
						// 만약 건설하여 이기는 건물이 첫번째라면, 더이상 진행하지 않고 그 건물을 올리는 시간만 더해준다.
					}
					if(buildtime[i] > max) {
						max = buildtime[i];
						// 첫 시작에서 가장 많이 시간이 걸리는 것을 기준으로 시작
					}
					
					dq.add(i);
				}
			}
			
			while( !dq.isEmpty() ) {
				int size = dq.size();
				// 한 시점에 걸리는 시간을 비교해야하는 개수
				max= -1;
				while(size>0) {
					size--;
					int now = dq.poll();
					for(int i = 0 ; i < node[now].size(); i++) {
						int next = node[now].get(i);
						time[next] = Math.max(time[now] + buildtime[next] , time[next]); 
						if(--degree[next]==0) {
							dq.add(next);
						}
					}
				}
			}
			sb.append((time[target-1]) +"\n");
			// 지으면 이기는 건물을 짓는 시간을 더해줌.
			dq.clear();
			// 다음 tc를 받기위해
		}System.out.println(sb);
	}
}

---

예외처리와 배열의 index는 꼭 체크해주어야한다.