백준 2056 - 작업 ( JAVA )

출처 - 백준 알고리즘

2056번: 작업

---

[ 알고리즘 ] 

: 각 작업에 대하여, 선행해야 할 작업이 있다면 완료 후 수행 

finished 일차원 배열을 하나 두어서, 해당 작업이 완료 되었다면, 완료 된 시간으로 갱신 

+ 즉, 탐색 할 때에 finished 값이 0 이라면, 아직 완료 되지 않은 작업이라는 것을 알 수 있음 !! 

▶ dp 문제임, 이전에 수행된 값을 배열에 저장해놓고, 이후의 연산에서 그 값을 활용하는 것 . memorization 

 

내가 생각한 전체 로직은 , 

1. 각 작업에 대하여, ( 작업번호 , 수행시간, 선행해야 할 작업 갯수, 선행목록-리스트 ) 클래스를 생성하여 큐에 삽입
2. 모든 작업에 대한 정보를 큐에 삽입했다면 , 큐가 모두 비어질 때까지 아래작업 반복 
   1. 큐에서 작업하나를 꺼내어, 해당 작업에 대해 선행되어야 할 작업이 있는지 확인한다 .
   2. 선행되어야 할 작업이 없다면, finished 값을 time(수행시간) 값으로 변경 → 바로 시작하자마자 수행하면 됨
   3. 선행되어야 할 작업이 있다면, 선행목록 리스트를 탐색하며 모두 선행이 완료 되었는지 확인한다 , 
   4. 만약 하나라도 finished 값이 0인 것이 있다면, 아직 선행이 완료 되지 않은 것이기 때문에, 다시 큐에 삽입 !! 
   5. 선행이 모두 수행되었다면, 리스트의 fnished  값 중에 최댓값을 찾는다 → 가장 늦게 끝난 것 이후에 수행 
      ex ) 5번 작업의 선행목록이 2, 4번일 때 [ 2 : 12 / 4 :15 가 종료시간 ]이라면, 15에 5를 수행할 수 있음 !! 
   6. 최댓값은 선행목록이 모두 수행된 시간이기 때문에 , 최댓값 + 현재 작업의 수행시간을 더해서 finished 값 갱신  
3. 큐가 모두 비어졌다면, 모든 작업이 완료된 것이므로, finished 값 중 최댓값을 찾아서 출력한다 ~ 

---

[ 코드 ] 

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

public class Solution_BaekJoon_2056_작업_골드5 {
	
	static class Work{
		int num; //몇번 작업 ?
		int time; // 소요시간 
		int preCount; // 선행되어야할 작업 갯수 
		List<Integer> list ; //선행작업 목록
		
		public Work(int num, int time, int preCount, List<Integer> list) {
			super();
			this.num = num;
			this.time = time;
			this.preCount = preCount;
			this.list = list;
		}
	}
	
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st; 
		Queue<Work> que = new LinkedList<>(); //수행해야 할 작업들

		int N = Integer.parseInt(br.readLine());
		int[] finished = new int[N+1]; //끝난시간 넣어주기 ( 0이 아니면 끝난거 ) 
		for(int i=1; i<=N; i++) {
			String s= br.readLine();
			st= new StringTokenizer(s, " "); 
			List<Integer> list = new ArrayList<>(); 
			
			int time= Integer.parseInt(st.nextToken()); 
			int pre = Integer.parseInt(st.nextToken()); 
			for(int p=0; p<pre; p++) {
				list.add(Integer.parseInt(st.nextToken()));
			}
			
			que.add(new Work(i,time,pre,list));
		}
		
		while(!que.isEmpty()) {
			Work now = que.poll();
			
			int num = now.num; 
			int time= now.time;
			int preCount = now.preCount; // 선행되어야할 갯수 
			if(preCount == 0) {
				// 선행되어야 할 것 없음 , 바로 수행 하면 됨 
				finished[num] += time; 
				continue;
			}
			List<Integer> list = now.list; // 선행되어야 할 수행 목록 
			boolean isAll = true; 
			int max=0; 
			//선행목록들이 다 수행되었는지 체크 isAll
			for(int i=0; i<list.size(); i++) {
				// finished 값이 0 이면, 아직 수행 다 안된 것 
				if(finished[list.get(i)]==0) {
					isAll = false;
					break; 
				}
				max=  Math.max(max, finished[list.get(i)]);
			}
			// 아직 선행이 다 안됬기 때문에, 조금 있다가 다시 수행해야 함 . 
			if(!isAll) {
				que.add(new Work(num, time, preCount, list)); 
			}
			// 선행이 다 됬음 
			else {
				finished[num] += (max + time); 
			}
			}
		
		int res = 0; 
		for(int i=0; i<finished.length; i++) {
			res = Math.max(res, finished[i]);
		}
		System.out.println(res);
	}
		
}