[BJ] 2056 : 작업 - unsolved

 

       문제 요약        

- 문제

https://www.acmicpc.net/problem/2056

 

 

         아이디어        

위상정렬 

위상정렬은 정렬 알고리즘의 일종으로 순서가 정해져있는 일련의 작업을 차례대로 수행해야 할 때 사용할 수 있는 알고리즘이다. 

비순환 방향 그래프 (DAG)에서 정점을 선형으로 정렬하는 것이다. 

 

 

         소스코드        

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

public class Main {
	static int N;
	static int[] times;
	static List<Integer> adj[];
	static int[] inDegree; // 위상정렬의 정의를 생각해보면, 진입차수가 0인 곳부터 너비탐색이 맞음
	static int[] dp; // 작업 i를 완료하는 데 걸리는 최소 시간 

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		times = new int[N + 1];
		adj = new ArrayList[N + 1];
		for (int n = 0; n < N + 1; n++) {
			adj[n] = new ArrayList<>();
		}
		inDegree = new int[N + 1];
		dp = new int[N + 1];
		for (int to = 1; to <= N; to++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			times[to] = Integer.parseInt(st.nextToken());
			int cnt = Integer.parseInt(st.nextToken()); //선행 작업 갯수
			for (int i = 0; i < cnt; i++) {
				int from = Integer.parseInt(st.nextToken()); // 선행 작업 번호
				adj[from].add(to); // FROM -> TO 방향으로 연결
				inDegree[to] += 1; // TO의 진입 차수 증가 
			}
		}

		Queue<Integer> queue = new ArrayDeque<>();
		for (int i = 1; i <= N; i++) {
			if (inDegree[i] == 0) {
				queue.add(i);
				dp[i] = times[i]; // 초기 작업 시간 설정 
			}
		}

		while (!queue.isEmpty()) {
			int now = queue.poll();
			for (int next : adj[now]) {
				inDegree[next] -= 1; // 후행 작업의 진입 차수 감소 
                // 후행 작업의 최소 시간 갱신
				dp[next] = Math.max(dp[next], dp[now] + times[next]);
                // 후행 작업의 진입 차수가 0이 되면 큐에 추가 
				if (inDegree[next] == 0) {
					queue.add(next);
				}
			}
		}

		int max = 0;
		for (int i = 1; i <= N; i++) {
			max = Math.max(max, dp[i]);
		}
		System.out.println(max);
	}

}