문제 설명

문제 분석

슈도코드

구현

public class 게임개발하기_1516 {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(reader.readLine()); //건물의 종류 수
        ArrayList<ArrayList<Integer>> building = new ArrayList<>();
        for (int i = 0; i <= N; i++) {
            building.add(new ArrayList<>());
        }

        int[] indegree = new int[N + 1]; //진입 차수
        int[] selfBuildTime = new int[N + 1]; //자기 자신을 짓는 데 걸리는 시간
        for (int i = 1; i <= N; i++) {
            StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
            selfBuildTime[i] = Integer.parseInt(tokenizer.nextToken());

            while (true) {
                int prev = Integer.parseInt(tokenizer.nextToken());
                if (prev == -1) break;

                building.get(prev).add(i); //인접 리스트 초기화
                indegree[i]++; //진입 차수 초기화
            }
        }

        //위상 정렬
        Queue<Integer> q = new LinkedList<>();
        for (int i = 1; i <= N; i++) {
            if(indegree[i] == 0) {
                q.add(i);
            }
        }

        int[] result = new int[N+1];
        while(!q.isEmpty()) {
            int curNode = q.poll();
            for (int next : building.get(curNode)) {
                indegree[next]--;
                //시간 업데이트
                result[next] = Math.max(result[next], result[curNode] + selfBuildTime[curNode]);
                if(indegree[next] == 0) {
                    q.add(next);
                }
            }
        }

        for (int i = 1; i <= N; i++) {
            System.out.println(result[i] + selfBuildTime[i]);
        }
    }
}