[백준 2056번] 작업 (java)

2056번: 작업

 

다이나믹 프로그래밍과 위상정렬을 이용하여 푸는 문제

먼저, 위상정렬을 이용하여 작업간의 순서를 빠른 순서대로 큐에 저장해둔다.

Queue<Integer> order =  new LinkedList<>();

 

그리고 dp 일차원 배열에는 작업의 최소 완료시간을 저장한다.

dp[n] : 작업 n을 완료하기 위해 필요한 최소 시간

 

큐에서 가장 먼저 실행되는 작업(n)부터 하나씩 꺼낸다.

dp[n] = dp[n] + time[n] 으로, dp[n]에 해당 작업의 소요시간(time[n])을 더해준다.

(제일 처음 큐에서 꺼내지는 작업은 0 + time[n] 이 될 것이다.)

 

해당 작업(n) 다음에 수행되어야할 작업(m)의 시작 시간을 갱신시켜준다.

dp[m] = Math.max(dp[m], dp[n])

Math.max()로 최대값을 구해서 dp[m]에 넣어주는 이유는

어떤 작업(m)이 있을 때, 그 작업 직전에 수행되는 여러 작업들 중 가장 늦게 끝나는 시간이 이 작업(m)의 시작시간이 되기 때문이다.

 

그리고 다음번에 큐에서 작업 m이 꺼내지게 되면

(m이 n보다 늦게 작업이 시작되므로 위상정렬을 하게 되면 n보다 늦게 큐에서 꺼내짐)

기존의 dp[m]에 소요시간(time[m])만 더해주면 되는 것이다.

 

아래 그림은 백준 2056번 문제 예제를 나타낸 것이다.

 

 

소스코드 : 

	import java.io.*;
	import java.util.*;
	public class n02056 {
	static int N, res;
	static Vector<Integer>[] v;
	static int[] indegree, dp, time;
	static Queue<Integer> order = new LinkedList<>();
	public static void main(String[] args) throws Exception {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	N = Integer.parseInt(br.readLine());
	dp = new int[N + 1];
	indegree = new int[N + 1];
	time = new int[N + 1];
	v = new Vector[N + 1];
	for (int i = 1; i <= N; i++)
	v[i] = new Vector<>();
	for (int i = 1; i <= N; i++) {
	String[] sarr = br.readLine().split(" ");
	time[i] = Integer.parseInt(sarr[0]);
	indegree[i] = Integer.parseInt(sarr[1]);
	for (int j = 0; j < indegree[i]; j++) {
	int m = Integer.parseInt(sarr[2 + j]);
	v[m].add(i);
	}
	}
	getOrder();
	while (!order.isEmpty()) {
	int n = order.poll();
	dp[n] += time[n];
	for (int m : v[n])
	dp[m] = Math.max(dp[m], dp[n]);
	res = Math.max(res, dp[n]);
	}
	bw.write(res + "\n");
	bw.flush();
	}
	public static void getOrder() {
	Queue<Integer> q = new LinkedList<>();
	for (int n = 1; n <= N; n++) {
	if (indegree[n] == 0)
	q.offer(n);
	}
	while (!q.isEmpty()) {
	int n = q.poll();
	order.offer(n);
	for (int m : v[n]) {
	indegree[m]--;
	if (indegree[m] == 0)
	q.offer(m);
	}
	}
	}
	}

view raw 2056.java hosted with ❤ by GitHub