위상정렬

• 문제의 조건이

  1. 순서가 정해져 있는 작업을 수행
  2. 그래프로 표현했을 때 사이클이 일어나지 않는 경우

경우에는 위상 정렬을 고려해보자.

알고리즘

• 큐 또는 스택으로 구현할 수 있다.
• 여기서는 큐를 사용한다.

1. 진입 차수가 0인 정점을 큐에 넣는다.
2. 큐에서 정점을 꺼내어 연결되어있는 모든 간선을 제거한다.
	2-1. 이때, 간선을 제거했을 때 진입차수가 0이 된 정점은 큐에 넣는다.
3. 큐가 빌때까지 2를 반복한다.

예시 문제

작업

• 간선을 표현할 때 이중 배열을 사용하면 메모리 초과가 발생한다.
• 이중 리스트를 사용하자.

public class J18_작업_sol2 {
	
	static BufferedWriter bw;
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		//
		int N = Integer.parseInt(br.readLine());
		int[] time = new int[N+1];
		int[] result = new int[N+1];
		int[] inputcount = new int[N+1];
		ArrayList<ArrayList<Integer>> work = new ArrayList<>();
		for (int i = 0; i < N+1; i++) {
			work.add(new ArrayList<>());
		}
		
		Queue<Integer> Q = new LinkedList<Integer>();
		
		for (int i = 1; i <= N; i++) {
			st = new StringTokenizer(br.readLine());
			
			time[i] = Integer.parseInt(st.nextToken());
			result[i] = time[i];
			
			int before = Integer.parseInt(st.nextToken());
			if ( before == 0 ) {
				// 제일 처음 해야할 일
				Q.add(i);
			} else {
				inputcount[i] = before;
				for (int j = 0; j < before; j++) {
					int beforeWork = Integer.parseInt(st.nextToken());
//					work[beforeWork][i] = 1;
					work.get(beforeWork).add(i);
				}
			}

		}
		
		while( Q.isEmpty() == false ) {
			
			int now = Q.poll();
			for (int i = 0; i < work.get(now).size(); i++) {
				int next = work.get(now).get(i);
				result[next] = Math.max(result[next], result[now] + time[next]);
				inputcount[next] -= 1;
				if ( inputcount[next] == 0 ) {
					Q.add(next);
				}
			}
		}
		
		int answer = 0;
		for (int i = 1; i < N+1; i++) {
			answer = Math.max(answer, result[i]);
		}
		bw.append(answer+"");
		bw.flush();
		bw.close();
		br.close();
	}
}