[백준] 1005 : ACM Craft

문제

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

 

특정 건물이 먼저 완성되어야 함

승리하기 위해 건물 W를 건설하는데 걸리는 최소 시간 구하기 

 

 

입출력

테스트 케이스 개수 T

건물 개수 N 건설 순서 규칙 개수 K

각 건물i의 건설 시간

건설 순서 규칙 X Y -> X를 지어야 Y를 지을 수 있음

목표 건물 W

 

 

---

아이디어

위상 정렬을 활용한 건설 순서 및 최소 시간 계산 문제 

 

위상 정렬 + DP 

1. 진입 차수 배열 indegree 생성 

- i번 건물을 짓기 전에 지어야 할 건물 개수

2. 그래프 생성

i번 건물 이후에 지어야 할 건물 목록

3. result

i번 건물이 완성되는 최소 시간

4. 위상 정렬 수행

indegree[i] == 0 인 건물부터 큐에 넣고 시작 

선행 건물이 모두 지어진 후 최대 시간을 기준으로 갱신

 

A <- B

A <- C 

이렇게 A에 도착한다고 할 때 A 건설하는 데 걸리는 시간은 최대 시간임

코드 

 

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	static int T; // 테스트케이스의 개수
	static int N, K; // 건물의 개수, 건물 간의 건설 순서 규칙의 총 개수
	static List<Integer> adj[];
	static int[] indegree;
	static int[] time;
	static int W;
	static boolean[] visited;

	public static void main(String[] args) throws Exception {
		System.setIn(new FileInputStream("src/input.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		T = Integer.parseInt(br.readLine()); // 테스트케이스의 수
		StringTokenizer st;
		for (int t = 0; t < T; t++) {
			st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken()); // 건물의 개수
			K = Integer.parseInt(st.nextToken()); // 건물 순서 규칙의 총 개수

			time = new int[N + 1];
			st = new StringTokenizer(br.readLine());
			for (int i = 1; i <= N; i++) {
				time[i] = Integer.parseInt(st.nextToken());
			}

			adj = new ArrayList[N + 1];
			for (int i = 0; i < N + 1; i++) {
				adj[i] = new ArrayList<>();
			}

			indegree = new int[N + 1];
			for (int k = 0; k < K; k++) {
				st = new StringTokenizer(br.readLine());
				int x = Integer.parseInt(st.nextToken());
				int y = Integer.parseInt(st.nextToken());
				adj[x].add(y);
				indegree[y] += 1;
			}
			int[] result = new int[N + 1];
			visited = new boolean[N + 1];
			W = Integer.parseInt(br.readLine()); // 승리하기 위해 건설해야 할 건물의 번호
			Queue<Integer> queue = new ArrayDeque<>();
			for (int i = 1; i <= N; i++) {
				if (indegree[i] == 0) {
					visited[i] = true;
					queue.add(i);
					result[i] = time[i];
				}
			}

			while (!queue.isEmpty()) {
				int now = queue.poll(); // 가장 앞에 있는 값을 뽑기

				for (int next : adj[now]) {
					if (visited[next]) {
						continue;
					}
					result[next] = Math.max(result[next], result[now] + time[next]); // 선행 건물이 처리될 때마다

					indegree[next] -= 1;
					if (indegree[next] == 0) {
						visited[next] = true;
						queue.add(next);
					}
				}
			}

			// 건설 완료하는 데 드는 최소 시간
			System.out.println(result[W]);
		}
	}

}