[Java] 백준 1005 ACM Craft

백준 1005 ACM Craft

풀이

예제 2번의 건설 순서를 그래프로 표현해보았습니다.
이 그림에서 결과값을 계산하는데 사용된 정점의 가중치는 색칠된 정점들의 가중치입니다.

그림을 보고 생각난 풀이는 다음과 같습니다.

1. 특정 건물을 건설하기 위해서는 자신을 가리키는 건물이 모두 지어져야 한다. 즉, 정점에 진입 간선이 없어야 건설이 가능하므로 위상 정렬을 사용한다.
2. 목표 건물까지 도달하는데 필요한 가중치의 합 중 가장 큰 값이 정답이 된다.
   → 이 시간보다 짦은 시간이 걸리는 경로는 해당 경로의 건물들이 모두 지어질 때까지 기다려야 목표 건물을 건설할 수 있기 때문이다.
3. 각 정점마다 해당 정점에 오는데 필요한 시간 합의 최댓값을 배열에 저장해둔다.

이렇게 생각을 정리하고 코드를 짜면 다음과 같습니다.

코드

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

//백준 1005 ACM Craft
public class b1005 {
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		
		for(int t = 0;t < T;t++) {
			String str[] = br.readLine().split(" ");
			int N = Integer.parseInt(str[0]);
			int M = Integer.parseInt(str[1]);
			
			ArrayList<Integer> graph[] = new ArrayList[N + 1];	// 위상 정렬을 위한 그래프
			for(int i = 0; i <= N;i++) {
				graph[i] = new ArrayList<>();
			}
			int inDegree[] = new int[N + 1];
			str = br.readLine().split(" ");
			
			int weight[] = new int[N + 1];
			int dp[] = new int[1001];	// 정점까지의 필요한 시간 합의 최댓값 저장할 배열
			
			for(int i = 0;i < str.length;i++) weight[i + 1] = Integer.parseInt(str[i]);
			
			int a, b;
			for(int i = 0;i < M;i++) {
				str = br.readLine().split(" ");
				a = Integer.parseInt(str[0]);
				b = Integer.parseInt(str[1]);
				
                // 간선을 추가하고 진입차수를 기록
				graph[a].add(b);
				inDegree[b]++;
			}
			
			int goal = Integer.parseInt(br.readLine());
			Queue<Integer> q = new ArrayDeque<>();
			
            //위상정렬을 하기 위해 진입차수가 0인 정점을 먼저 큐에 삽입
			for(int i = 1;i <= N;i++) {
				if(inDegree[i] == 0) {
					q.add(i);
					dp[i] = weight[i];	// 가장 처음 큐에 들어오는 정점은 최댓값이 자기 자신
				}
			}
			
            
			while(!q.isEmpty()) {
				int cur = q.poll();
			
				if(cur == goal) break;
				
				for(int i = 0;i < graph[cur].size();i++) {
					int node = graph[cur].get(i);
					dp[node] = Math.max(dp[node], dp[cur] + weight[node]);	// node라는 정점까지의 최댓값 구하기
					// 이 때, 진입차수가 0이 되지 않더라도 최댓값은 구해줘야 한다는 점에 유의
					
					if(--inDegree[node] == 0) {
						q.add(node);
					}
				}
			}
			
			
			System.out.println(dp[goal]);
		}
	}
}

• cur이 목표 정점이 된다는 것은 목표 정점을 건설하기 위해 지어야 하는 모든 건물을 건설했다는 뜻이므로 그 시점에 while문을 빠져나와 종료하고 결과값을 출력하면 됩니다.