[백준] 2056 작업 - 위상정렬 Topology Sort JAVA

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

2056번: 작업

코드설명

위상정렬 문제입니다.

 

위상정렬이란 방향그래프의 모든 노드를 '방향성에 거스르지 않도록 순서대로 나열하는 것' 입니다. 

이 과정에서 만약 작업 순서를 단순하게 출력한다면 정말 일반적인 위상정렬 문제입니다.

문제에서 요구하는 답은 모든 작업을 완료하기 위한 최소시간을 구해야합니다.

 

제가 문제를 풀며 헷갈렸던 점은, 주어진 작업들을 연속적으로 그래프로 연결하여 진행해야하는 줄 알았습니다.

문제의 예제 입력을보면

7
5 0
1 1 1
3 1 2
6 1 1
1 2 2 4
8 2 2 4
4 3 3 5 6

만약 5번째 작업인 1 2 2 4 를 보면,  2 -> 4 -> 1 이 아닌, 2 -> 1 이면서 4 - > 1 의 작업이라고 생각하면 됩니다.

단순하게, 문제에 주어진 k번 작업을 시작하기 전에 반드시 먼저 완료되어야하는 작업들이라고 이해해야합니다.

 

각각의 작업을 완료하기 위해 필요한 최소시간은,  longestTime[N+1] 에 저장합니다.

최소시간을 구하는것인데 longestTime 을 Max값으로 갱신시키는 이유는 해당 작업의 선행작업이 모두 끝나기 전에 다음 작업을 수행할 수 없기에 그렇습니다. 최소 시간을 구할경우 더 적게 걸리는 시간을 갱신하여 결국 각각의 작업이 끝나는 시간을 올바르게 갱신할 수 없습니다.

예를들어, 3번 작업이 존재하고, 3번 작업의 선행조건으로 1번작업과 2번 작업이 존재한다고 가정합니다.

1번 작업은 100초 가 걸립니다. 2번 작업은 200초가 걸립니다. 3번작업은 200초가 필요합니다.

longestTime[nodeB]= Math.max(longestTime[nodeB], longestTime[now] + time[nodeB]);

위의 점화식을 설명해보면,

longestTime[nodeB] : now 작업이 끝나고 다음 nodeB 작업이 종료되는데 걸리는시간을 의미합니다.

Math.max(longestTime[nodeB], longestTime[now] + time[nodeB]) : nodeB의 걸리는 시간과   now의 걸리는 시간과 nodeB를 완료하는데 작업하는 시간의 합의 최대값을 구합니다. 이를 통해 모든 작업이 끝나는데 걸리는시간을 갱신해나갈 수 있습니다.

 

즉, longestTime[now] 현재 now 번째 작업의 시간을 구하는것이 아니라, now와 연결된 nodeB의 시간을 미리 구함으로써 작업시간을 구해나갑니다.

 

위상정렬에서 모든 작업이 종료되는데 걸리는 최소시간을 구하는 문제였습니다.

만약 모든 작업이 아닌, 마지막 노드의 작업이 걸릴경우 아래와 같이 배열을 활용하지 않아도 됩니다.

코드

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 int N, M;
	public static int answer = 0;
	public static ArrayList<ArrayList<Node>> graph = new ArrayList<ArrayList<Node>>();
	public static int[] inDegree;
	public static int[] time;
	public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	N = Integer.parseInt(st.nextToken());
    	for(int i=0;i<=N;i++) {
    		graph.add(new ArrayList<Node>());
    	}
    	inDegree = new int[N+1];
    	time = new int[N+1];
    	
    	for(int i=1; i<=N; i++) {
    		st = new StringTokenizer(br.readLine());
    		time[i] = Integer.parseInt(st.nextToken());
    		int cnt = Integer.parseInt(st.nextToken());
    		
    		for(int j=0;j<cnt;j++) {
    			int nodeB = Integer.parseInt(st.nextToken());
    			graph.get(nodeB).add(new Node(i));
				inDegree[i] += 1;
    		}
    		
    	}
    	
    	topologySort();
	}
	
	public static void topologySort() { //위상정렬 시작.
		ArrayList<Integer> result = new ArrayList<>();
		Queue<Integer> q = new LinkedList<>();
		int[] longestTime = new int[N+1]; //각 작업별 가장 오래갤
		
		
		for(int i=1;i<=N;i++) {
			longestTime[i] = time[i]; 		//각 작업별로 가장 오래걸리는 시간의 초기값은 본인의 작업시간으로 선정합니다. 이는 이후에 가장 첫번째 값 혹은 아무 작업이 없는 작업이 존재할때 유용합니다.
			if(inDegree[i] == 0) { //만약 진입차수가 0 개라면 시작점입니다.
				q.offer(i);	
			}
		}
		
		while(!q.isEmpty()) {
			
			int now = q.poll();
			for(int i=0;i<graph.get(now).size();i++) {
				int nodeB = graph.get(now).get(i).nodeB;
				inDegree[nodeB] -= 1;
				longestTime[nodeB]= Math.max(longestTime[nodeB], longestTime[now] + time[nodeB]);
				if(inDegree[nodeB] == 0 ) {
					q.offer(graph.get(now).get(i).nodeB);
				}
			}
		}
		
		for(int i=1;i<=N;i++) {
			answer = Math.max(longestTime[i], answer);
		}
		System.out.println(answer);
		
	}
	
	
}

class Node{
	int nodeB;
	public Node(int nodeB) {
		this.nodeB = nodeB;
	}
}