백준 1005 - ACM Craft (java) (수정)

문제 링크

접근

건물 짓기가 순서대로 진행되며, 우선된 것을 하기 전까지는 후의 건물을 지을 수 없다는 점에서 위상정렬 문제라는 것을 알 수 있음

시행착오

위상정렬을 통해 각 레벨마다 필요한 가장 큰 시간을 저장해 풀었지만, A 루트의 세번째 건물 건설시간이 10이라고 할 때, B 루트의 두번째 건물 건설시간이 15라면 레벨별 최댓값을 찾는 방법은 틀림

풀이

각 건물에 대한 현재까지 걸리는 시간을 Math.max로 업데이트시키며 저장한 후, 마지막에 짓는 건물의 진입차수가 0일 때 출력

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class BOJ1005 {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] str = br.readLine().split(" ");
		int testCase= Integer.parseInt(str[0]);
		int n, k, x, y, last, tmp, idx;
		int[] time, timeAll, inCnt;
		ArrayList<Integer>[] graph;
		Queue<Integer> que = new LinkedList<>();
		StringBuilder sb = new StringBuilder();
		
		while(testCase-->0) {
			str = br.readLine().split(" ");
			//건물의 수와 건물 간선 수 입력
			n = Integer.parseInt(str[0]);
			k = Integer.parseInt(str[1]);
			time = new int[n+1];
			timeAll = new int[n+1];
			inCnt = new int[n+1];
			
			//각 건물당 건설시간 받기
			str = br.readLine().split(" ");
			for(int i = 0; i < n; i++) {
				time[i+1] = Integer.parseInt(str[i]);
			}
			
			//그래프 만들기
			graph = new ArrayList[n+1];
			for(int i = 1; i <= n; i++) {
				graph[i] = new ArrayList<>();
			}
			for(int i = 0; i < k; i++) {
				str = br.readLine().split(" ");
				x = Integer.parseInt(str[0]);
				y = Integer.parseInt(str[1]);
				graph[x].add(y);
				inCnt[y]++;
			}
			
			//마지막에 짓는 건물 입력받기
			last = Integer.parseInt(br.readLine());
			if(inCnt[last] == 0) {
				sb.append(time[last]).append('\n');
				continue;
			}
			
			que.clear();
			//진입차수가 0인 것들 que에 넣은 후, 걸리는 시간 수정
			for(int i = 1; i <= n; i++) {
				if(inCnt[i] == 0) {
					que.add(i);
					timeAll[i] = time[i];
				}
			}
			
			//위상정렬
			while(!que.isEmpty() || inCnt[last] != 0) {
				tmp = que.poll();
				//현재 간선들 따라가면서 총 걸리는 시간 수정
				for(int i = 0; i < graph[tmp].size();i++) {
					//현재까지 걸리는 시간 수정
					idx = graph[tmp].get(i);
					timeAll[idx] = Math.max(timeAll[idx], timeAll[tmp]+time[idx]);
					inCnt[idx]--;
					//진입차수 0일 때 큐에 추가
					if(inCnt[idx] == 0) {
						que.add(idx);
					}
				}
			}
			
			sb.append(timeAll[last]).append('\n');			
		}
		System.out.println(sb);
	}
}