[백준] 1516 : 게임 개발 - JAVA

🙋🏻‍♀️ 위상정렬 이용!

각각 건물이 지어지기까지의 시간을 구하는게 헷갈렸다.

처음에는 q.poll()을 하면 해당 건물을 들리는(완성하는)것이라서 그때마다 답 배열의 해당 건물인덱스에 '답 배열속 해당 건물의 값 + 해당 건물을 짓는데 걸리는시간'을 더했었다.
나름 누적하는걸 생각해서 짰는데, 답이 전혀 이상하게 나왔다...

이렇게 하면 완성되는 그 시점에서 해당 건물 하나만 시간을 계산하기때문에, 누적이 되지않는것이다.

해설을 참고했다.

시간 로직

각 건물을 완성하는데 걸리는 시간을 구하는 방법(정답 배열 업데이트 방법)

• Math.max(현재 건물(노드)에 저장된 최대 시간, 이전 건물(노드)에 저장된 최대 시간 + 현재 건물(노드)의 생산 시간)

이때 정답배열은 특정노드의 모든 인접노드의 진입차수를 -1씩 해주는데, 이렇게 작업하는 모든 인접노드에 대해 수행한다!
(따라서, 나가는 에지가 없으면 정답배열은 갱신될 일이 없다.)

또한 정답 배열에 자기 건물을 짓는데 걸리는 시간을 마지막에 더해야한다!

내 풀이

import java.util.Scanner;
import java.util.ArrayList;
import java.util.Queue;
import java.util.LinkedList;

public class  Main {
public static ArrayList<Integer> list[];
public static int time[];
public static int answer[];
public static int indegree[];
public static int N;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		time = new int[N+1];
		list = new ArrayList[N+1];
		indegree = new int[N+1];
		answer = new int[N+1];
		for(int i=0; i<N+1; i++) {
			list[i] = new ArrayList<Integer>();
		}
		for(int i=1; i<N+1; i++) {
			time[i] = sc.nextInt();
			int before = sc.nextInt();
			while(before != -1) {
				list[before].add(i);
				indegree[i]++;
				before = sc.nextInt();
			}
		}
		topologicalSort(time,list);
		for(int i=1; i<answer.length; i++) {
			System.out.println(answer[i]);
		}
	}
	
	public static void topologicalSort(int[] time, ArrayList<Integer>[] list) {
		Queue<Integer> q = new LinkedList<>();
		for(int i=1; i<N+1; i++) {
			if(indegree[i] ==0) {
				q.add(i);
			}
		}
		while(!q.isEmpty()) {
			int here = q.poll();
			for(int n : list[here]) {
				if(--indegree[n] ==0) {
					q.add(n);
				}
				answer[n] = Math.max(answer[n], answer[here] + time[here]); //이 부분이 헷갈리니 주의하자 
			}
		}
		for(int i=1; i<N+1; i++) {
			answer[i] += time[i];
		}
	}

}