[백준] 2056 작업

1. 문제

www.acmicpc.net/problem/2056

2056번: 작업

2. 접근방법

그래프와 bfs만 이용해서 풀었는데 풀고보니 분류에 DP라 되어 있네 ;;

dp 방법은 생각 안해봤지만 우선 bfs로 푸는 방법은

 

우선 1번과 2번은 바로 일을 시작 가능하기 때문에 큐에 바로 넣어 준다.

 

큐의 size를 저장하고 그만큼만 돌면서 1시간동안 동시에 하는 작업을 나타내고

 

1번의 작업시간과 2번의 작업시간 1씩 줄이고 다시 큐에 넣는다.

 

계속 돌리다

1번의 작업이 다 끝나면 자식인 3,4 를 큐에 넣어준다. ( 입력으로는 자식 - 부모 형태로 주니 부모 - 자식으로 바꿔서 넣는다)

 

3번이 끝나면 8번을 넣어야 하는데 다른 부모들도 다 끝나야 8번의 일을 시작할 수 있기 때문에

부모 - 자식으로 저장할 때 8번의 부모의 갯수를 세어서 배열에 저장해둔다.

 

3번이 끝나고 8번을 넣을 때 8번의 부모 하나를 줄이고 부모가 아직 남아 있다면 큐에 넣지 않는다.

 

나중에 4번이 끝나고 8번의 부모를 하나 더 줄이고

5번이 끝나고 8번의 부모를 하나 더 줄이면 0이 되어 8이 일을 시작 할 수 있기 때문에 그 때 큐에 넣는다.

 

이런 식으로 1시간 씩 진행 시켜가며

큐에 있는 모든 작업이 완료 되면 종료하면 된다.

 

3. 자바 코드

package Gold;

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

public class G4_2056작업 {
	
	static int [] parentcnt,time;
	
	static int N;
	static ArrayList<ArrayList<Integer>> nodearr = new ArrayList<>();
	static Queue<Integer> que = new LinkedList<Integer>();
	static int ans;
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		N = Integer.parseInt(br.readLine());
		time = new int[N];
		parentcnt = new int[N];
		for(int i = 0 ; i < N ; i++)
			nodearr.add(new ArrayList<>());
		
		for(int i = 0 ; i < N ; i++) {
			st = new StringTokenizer(br.readLine());
			int n = Integer.parseInt(st.nextToken());
			time[i] = n;
			n = Integer.parseInt(st.nextToken());
			if(n == 0)
				que.offer(i);
			for(int j = 0 ; j < n ; j++) {
				int ch = Integer.parseInt(st.nextToken())-1;
				nodearr.get(ch).add(i);
				parentcnt[i]++;
			}
		}
		bfs();
		System.out.println(ans);
		
	}
	static void bfs() {
		
		while(!que.isEmpty()) {
			for(int s = que.size() ; s> 0 ; s--) {
				int now = que.poll();
				time[now]--;
				if(time[now] != 0) {
					que.offer(now);
					continue;
				}
				
				for(int i : nodearr.get(now)) {
					parentcnt[i]--;
					if(parentcnt[i] == 0)
						que.offer(i);
				}
			}
			ans++;
		}
	}

}

4. 마치며

DP로는 어떻게 푸는걸까 ..