[Java] 백준 2056번 : 작업*

1. 문제

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

2056번: 작업

 

 

 

2. 풀이과정

풀이방법은 2가지가 있다. 위상 정렬 문제를 많이 접해보지 않아서 헤맸던 문제다.

 

1. 위상정렬

선행 요소를 입력 받을 때, 선행요소에  '나'를 추가하는 방식으로 한다. 즉, 모든 노드들의 후행요소로 저장해주는 것이다.

0번째 작업부터 차례대로 돌면서, 자신의 뒤에 실행할 곳에 수행 시간을 더해준다.이때, 선행 요소가 여러 개 있는 작업은 수행 시간이 가장 긴 선행 요소 다음에 실행 되므로 max값을 저장한다.

import java.io.*;
import java.util.*;

public class Main {
	static int N;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		LinkedList<Integer> list[] = new LinkedList[N];
		int cost[] = new int[N], degree[] = new int[N], result[] = new int[N];
		boolean visited[] = new boolean[N];
		Queue<Integer> q = new LinkedList<>();
		
		for(int i=0; i<N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			cost[i] = Integer.parseInt(st.nextToken());
			list[i] = new LinkedList<>();
			degree[i] = Integer.parseInt(st.nextToken());
			if(degree[i]==0) {
				visited[i]=true;
				q.add(i);
				result[i] = cost[i];
				continue;
			}
			for(int j=0; j<degree[i]; j++) {
				list[Integer.parseInt(st.nextToken())-1].add(i);
			}
		}
		
		while(!q.isEmpty()) {
			int now = q.poll();
			for(int next : list[now]) {
				result[next] = Math.max(result[next], result[now]+cost[next]);
				if(--degree[next]==0) {
					q.add(next);
				}
			}
		}
		
		int ans=0;
		for(int i=0; i<N; i++) {
			ans = Math.max(ans, result[i]);
		}
		System.out.println(ans);
	}

}

 

 

 

2. DP

자기 자신 = max(자기자신, 선행 요소 걸리는 시간+자기가 걸리는 시간)으로 업데이트 해간다.

K번 작업에 대해 선행 관계에 있는 작업들의 번호가 K보다 무조건 작기 때문에, 입력을 받으면서 동시에 수행해주었다.

import java.io.*;
import java.util.*;

public class Main {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int cost[] = new int[N], result = 0;
		
		for(int i=0; i<N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int time = Integer.parseInt(st.nextToken());
			int degree = Integer.parseInt(st.nextToken());
			cost[i] = time;
			for(int j=0; j<degree; j++) {
				int f = Integer.parseInt(st.nextToken())-1;
				cost[i] = Math.max(cost[i], cost[f]+time);
			}
			result = Math.max(result, cost[i]);
		}
		System.out.println(result);
	}
}