2056_작업 **

사용 알고리즘: 위상정렬

사용 언어: java

 

최소 시간을 구해라...? 일단 위상정렬만 구현해 봄

package week04;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Queue;
import java.util.Scanner;

public class Main_bj_2056_작업 {

	static int n; //작업 개수
	static int[] workTime; //각 작업 걸리는 시간, 크기 n+1
	static ArrayList<Integer>[] nxtWorks; //각 작업의 선행 작업, 크기 n+1
	static int[] inputCnt; //선행 작업의 개수, 크기n+1 (위상 정렬에 필요)
	static Queue<int[]> q = new ArrayDeque<>(); //{작업 번호, 필요 작업 시간}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		workTime = new int[n+1]; //각 작업 걸리는 시간
		inputCnt = new int[n+1]; //선행 작업의 개수
		
		nxtWorks = new ArrayList[n+1];
		for (int i = 0; i < n+1; i++) {
			nxtWorks[i] = new ArrayList<>();
		}
		
		for(int start = 1; start < n+1; start++) {
			workTime[start] = sc.nextInt();
			
			int cnt = sc.nextInt();
			if (cnt == 0) { //선행 작업이 없으면 큐에 넣기
				q.add(new int[] {start, workTime[start]});
			}
			inputCnt[start] = cnt;
			
			for (int i = 0; i < cnt; i++) {
				int nxtWork = sc.nextInt();
				nxtWorks[nxtWork].add(start);
			}
			
			Collections.sort(nxtWorks[start]);
		}
		//입력 끝
		
//		System.out.println(Arrays.toString(workTime));
//		System.out.println(Arrays.toString(inputCnt));
//		System.out.println(Arrays.toString(nxtWorks));
		
		topology();
	}

	private static void topology() {
		int ans = 0;
		boolean[] visit = new boolean[n+1];
		
		while(!q.isEmpty()) {
			int[] p = q.poll();
			visit[p[0]] = true;
			
			ans = Math.max(ans, p[1]);
			
			for(int nxt : nxtWorks[p[0]]) {
				inputCnt[nxt] -- ;
				if(inputCnt[nxt] == 0) {
					q.add(new int[] {nxt, p[1] + workTime[nxt]});
				}
			}
		}
		
		System.out.println(ans);
	}

}

 

위의 코드대로 하면

3
5 0
2 0
3 2 1 2

이 예시에서 답이 5로 나옴... 답은 5 + 3 = 8이 나와야 하는데...

ans가 이미 5일 때, ans = Math.max(5, 2+3)가 되기 때문에 틀리게 된다.

 

메모이제이션을 활용해, 해당 부분을 갱신해준다.

 

 

통과 코드

package week04;

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

public class Main_bj_2056_작업 {

	static int n; //작업 개수
	static int[] workTime; //각 작업 걸리는 시간, 크기 n+1
	static ArrayList<Integer>[] nxtWorks; //각 작업의 선행 작업, 크기 n+1 {작업 번호, 작업 시간}
	static int[] inputCnt; //선행 작업의 개수, 크기n+1 (위상 정렬에 필요)
	static Queue<Integer> q = new ArrayDeque<>(); //{작업 번호, 필요 작업 시간}
	/**
	 * 3
	 * 5 0
	 * 2 0
	 * 3 2 1 2
	 * 위의 예시에서 답은 8인데, 5가 나오는 문제.
	 * 메모이제이션 활용
	 */
	static int[] memo; //각 작업 수행이 완료될 떄, 가장 긴 시간 저장.
	
	public static void main(String[] args) {
		input_2056();
		
//		for(ArrayList<Integer> nn : nxtWorks) {
//			System.out.println(nn.toString());
//		}
		
		memo = new int[n];
		
		for (int i = 0; i < n; i++) {
			if(inputCnt[i] == 0) { 
				memo[i] = workTime[i];
				q.add(i); //선행 작업이 없는 작업부터 넣기
			}
		}
		
		while (!q.isEmpty()) {
			int cur = q.poll();
			
			for(int nxt : nxtWorks[cur]) {
				inputCnt[nxt] -- ;
				
				memo[nxt] = Math.max(memo[nxt], memo[cur] + workTime[nxt]);
				
				if(inputCnt[nxt] == 0) {
					q.add(nxt);
				}
			}
		}
		
		int ans = memo[0];
		for (int i = 1; i < n; i++) {
			ans = Math.max(ans, memo[i]);
		}
		System.out.println(ans);
	}

	private static void input_2056() {
		Scanner sc = new Scanner(System.in);
		
		n = sc.nextInt();
		workTime = new int[n];
		nxtWorks = new ArrayList[n];
		for (int i = 0; i < n; i++) {
			nxtWorks[i] = new ArrayList<>();
		}
		inputCnt = new int[n];
		
		for (int i = 0; i < n; i++) {
			workTime[i] = sc.nextInt();
			
			int cnt = sc.nextInt();
			
			for (int j = 0; j < cnt; j++) {
				int prev = sc.nextInt() - 1;
				
				/**
				 * i가 끝나면 j를 시작할 수 있는데,
				 * i -> j 형식으로 리스트를 구성하면, 처음 q에 들어간 애들 외에
				 * 더 들어갈 수가 없음
				 */
				
				nxtWorks[prev].add(i);
				inputCnt[i]++;
			}
		}
		
		
	}

	
}

 

진짜 여러모로 헷갈리는 문제... 아이디어 내는 거 자체가 어렵지는 않은데

뭔가 많이 헷갈렸다...