알고리즘105 :: BOJ_2056_작업

위상정렬과 관련된 문제입니다. 

"몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해 반드시 먼저 완료되어야 할 작업들이 있다." 

앞서 수행해야 하는 작업이 우선 수행한뒤 뒤에 노드들이 수행되어야 합니다. 따라서 위상정렬 알고리즘을 활용하여 해결할 수 있습니다.

		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		ArrayList<Integer>[] al = new ArrayList[n+1];
		for(int i=1; i<=n; i++)
			al[i] = new ArrayList<>();
        //입출력 관련된 부분입니다. 그래프의 연결관계를 나타내기 위해 어레이 리스트를 사용하였습니다. 

		int[] work = new int[n+1];
		int[] d = new int[n+1];
		int[] indegree = new int[n+1];
		//work 는 비용, d는 작업의 비용을 업데이트 합니다. ?작업의 비용이란 예를들어 한 노드에서
        다음 노드로 가리키는 방향이 여러개라면 다음 노드는 이전 노드 모두를 수행한뒤 처리해야 하기 때문에
        이 시간을 업데이트 해줄 배열 입니다. 
        for(int i=1; i<=n; i++) {
			work[i] = sc.nextInt();
			int cnt = sc.nextInt();
			for(int j=0; j<cnt; j++) {
				int k = sc.nextInt();
				al[k].add(i);
				indegree[i]++;
                //k노드 다음에 i가 존재한다. 따라서 i에는 indegree를 하나 증가시켜줍니다. 
			}
		}//end of for loop

		Queue<Integer> q= new LinkedList<>();
		for(int i=1; i<=n; i++) {
			if(indegree[i] == 0) {
            //인디그리가 0인 노드들에 대해 큐에 집어넣어 줍니다. 
				q.add(i);
				d[i] = work[i];
                //d 배열의 값을 work 각각에 대한 값으로 업데이트 합니다. 
			}
		}//end of for loop

		while(!q.isEmpty()) {
			int first = q.poll();
			for(int s : al[first]) {
				indegree[s]--;
                //간선을 끊는것을 사실상 -1 감소하는것으로 처리합니다. 
				if(indegree[s]==0) {
					q.add(s);
				}
                //인디그리가 0인것을 큐에 넣습니다. 
				if(d[s]<d[first]+work[s])
					d[s] = d[first]+work[s];
                //연결된 값중에서 Q1. 어느 간선의 가중치 값이 큰지 상관없이 우선 끝나는게 중요하니까
                사실상 값은 의미없는것이 아닌가?
			}
		}
		int ans = Integer.MIN_VALUE;
		for(int i=1; i<=n; i++) {
			ans = Math.max(ans, d[i]);
		}
		System.out.println(ans);

ㅡ. 통합

import java.util.*;
public class Main {
 
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		ArrayList<Integer>[] al = new ArrayList[n+1];
		for(int i=1; i<=n; i++)
			al[i] = new ArrayList<>();
		
		int[] work = new int[n+1];
		int[] d = new int[n+1];
		int[] indegree = new int[n+1];
		for(int i=1; i<=n; i++) {
			work[i] = sc.nextInt();
			int cnt = sc.nextInt();
			for(int j=0; j<cnt; j++) {
				int k = sc.nextInt();
				al[k].add(i);
				indegree[i]++;
			}
		}//end of for loop
		
		Queue<Integer> q= new LinkedList<>();
		for(int i=1; i<=n; i++) {
			if(indegree[i] == 0) {
				q.add(i);
				d[i] = work[i];
			}
		}//end of for loop
		
		while(!q.isEmpty()) {
			int first = q.poll();
			for(int s : al[first]) {
				indegree[s]--;
				if(indegree[s]==0) {
					q.add(s);
				}
				if(d[s]<d[first]+work[s])
					d[s] = d[first]+work[s];
			}
		}
		int ans = Integer.MIN_VALUE;
		for(int i=1; i<=n; i++) {
			ans = Math.max(ans, d[i]);
		}
		System.out.println(ans);
	}
}