[백준] 2056. 작업 (Java)

 

🔒 문제

2056번: 작업

 

🔑 알고리즘

다이나믹 프로그래밍(DP), 위상 정렬

 

💡  풀이

작업에 선행 관계가 있고, "K번 작업의 선행 작업은 1에서 K-1번 사이", 즉 사이클이 없다는 조건이 있으므로 위상 정렬을 이용하였다.

 

각 작업에 걸리는 시간을 배열에 저장하고

입력으로 그래프를 생성 후 진입 차수가 0인 작업(선행 작업이 없는 작업)을 큐에 삽입한다.

 

그리고 위상 정렬을 진행한다.

- 1. 큐에서 꺼낸 작업은 작업이 끝난 셈으로 해당 작업을 선행 작업으로 필요로 했던 작업들을 탐색하면서 진입 차수를 1 감소시키고

그 작업들의 현재 저장된 [선행 작업이 끝나는 가장 늦은 시간]을 [현재 작업이 끝난 시간]과 비교하여 최댓값으로 갱신한다.

 

- 2. 진입 차수가 0이 되었다면 선행 작업이 모두 완료된 것으로, 해당 작업을 큐에 삽입하고 해당 작업이 끝나는 시간을 max값과 비교하여 갱신한다.

 

위상 정렬이 끝났다면 모든 작업이 끝난 것이므로 저장된 max 값을 출력한다.

 

다음은 예제 입력에 대한 그래프이다.

 

✏️ 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int N = Integer.parseInt(br.readLine());

		ArrayList<Work>[] graph = new ArrayList[N + 1];
		for (int i = 1; i <= N; i++)
			graph[i] = new ArrayList<>();
		int[] inDegree = new int[N + 1];
		int[] timeList = new int[N + 1];
		int[] startTime = new int[N + 1];

		for (int i = 1; i <= N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");

			timeList[i] = Integer.parseInt(st.nextToken());
			int m = Integer.parseInt(st.nextToken());
			inDegree[i] = m;

			for (int j = 0; j < m; j++) {
				int b = Integer.parseInt(st.nextToken());
				graph[b].add(new Work(i, 0));
			}
		}

		int max = Integer.MIN_VALUE;
		Queue<Work> queue = new LinkedList<>();
		for (int i = 1; i <= N; i++) {
			if (inDegree[i] == 0) {
				queue.add(new Work(i, 0));
				max = Math.max(max, timeList[i]);
			}
		}
		
		while (!queue.isEmpty()) {
			Work cur = queue.poll();

			for (Work next : graph[cur.id]) {
				startTime[next.id] = Math.max(startTime[next.id], cur.time + timeList[cur.id]);
				
				if (--inDegree[next.id] == 0) {
					queue.add(new Work(next.id, startTime[next.id]));
					max = Math.max(max, startTime[next.id] + timeList[next.id]);
				}
			}
		}

		System.out.println(max);
	}

	static class Work {
		int id, time;

		public Work(int id, int time) {
			this.id = id;
			this.time = time;
		}
	}
}