[백준] 1516 게임 개발 - DP + 위상 정렬(Topology Sort) JAVA

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

1516번: 게임 개발

코드설명

위상정렬과 DP를 활용하는 문제입니다.

 

위상정렬에 대해 알고있다면 쉽게 해결할 수 있습니다.

문제에서 반례는 아래의 글을 참고했습니다.

https://www.acmicpc.net/board/view/37786

 

오류가 났었던 부분은, 하나의 건물을 짓고 나서 매번 연결된 건물들의 건설 시간을 갱신시켜야 합니다.

하지만, 처음에는 진입차수가 0 일때만 갱신해주어서 처음에 지어진 건물이 더 오랜 시간이 걸릴 수 있는데 무조건 마지막에 지어진 건물을 기준으로 시간을 갱신시켜서 올바르게 건물이 지어지는 시간을 계산하지 못했습니다.

코드

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 T, N, M;
	public static int[] timeAnswer = new int[501];
	public static ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();
	public static int[] time = new int[501];
	public static int[] inDegree = new int[501];
	public static int answer = 0;
	public static StringBuilder sb = new StringBuilder();
	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<Integer>());
    	}
    	
    	for(int i=1;i<=N;i++) {
    		st = new StringTokenizer(br.readLine());
    		int timeInput = Integer.parseInt(st.nextToken()); //해당 건물을 짓는데 걸리는 시간.
    		time[i] = timeInput;
    		while(true) {
        		int beforeConstruct = Integer.parseInt(st.nextToken());
        		if(beforeConstruct == -1)	break;
        		inDegree[i] += 1; //i번째에는 진입차수가 늘어난다. (i번째 건물을 짓기 위해 먼저 지어져야하는 건물이 증가하는 것이므로)
        		graph.get(beforeConstruct).add(i); //beforeConstruct graph에 i번째 건물을 연결한다.
    		}
    	}

    	Queue<Integer> q = new LinkedList<>();
    	for(int i=1;i<=N;i++) {
    		if(inDegree[i] == 0) { //만약 진입차수가 0 이라면 시작점이다.
    			timeAnswer[i] = time[i];
    			q.offer(i);	
    		}
    	}
    	
    	while(!q.isEmpty()) {
     		int temp = q.poll(); //건물을 1개 완성시킨다.
    		for(int i=0; i<graph.get(temp).size();i++) {
    			inDegree[graph.get(temp).get(i)] -= 1;
    			timeAnswer[graph.get(temp).get(i)] = Math.max(timeAnswer[graph.get(temp).get(i)], timeAnswer[temp] + time[graph.get(temp).get(i)]); // ==0 일때 하는것이 아닌 매번 끝날떄마다 갱신해주어서 연결된 건물의 삭제 순서에 영향을 받지 않도록 합니다. 
    			if(inDegree[graph.get(temp).get(i)] == 0) { //만약 진입차수가 0 개라면 해당 숫자를 Queue에 넣습니다.
//    				timeAnswer[graph.get(temp).get(i)] = Math.max(timeAnswer[graph.get(temp).get(i)], timeAnswer[temp] + time[graph.get(temp).get(i)]); // 이렇게 할경우 마지막에 연결된 것을 없앨때의 기준으로 위상정렬이 진행되어 올바르게 시간이 계산되지 않습니다.
    				q.offer(graph.get(temp).get(i));
    			}
    		}
    	}
    	
    	for(int i=1;i<=N;i++) {
    		System.out.println(timeAnswer[i]);
    	}
    	
	}
	
}