[백준] 1516. 게임 개발(Java)

문제

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

 

풀이

선행 조건을 해결해야하는 문제 특성상 위상정렬을 이용해서 문제를 해결했습니다.

입력을 받으면서, 정보를 저장했으며(진입차수, 건물 건설시간, 선행 건설 건물정보)

진입차수가 0인 건물을 큐에 넣고 그래프 탐색을 진행했습니다.

 

이때, 건물이 동시에 지어질 수 있기 때문에

건물 중 가장 오래걸리는 시간을 찾아서 ans 정답 배열에 저장해주었고

진입차수를 1 감소시킨 값이 0이라면 큐에 넣어주었습니다.

 

그래프 탐색을 마친 후

건물을 순회하면서 도출된 정답 배열 값 + 현재 건물을 건설하는 데 걸리는 시간을 더해주어 출력했습니다.

 

코드

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

public class Main {
    static int N;
    static int[] topologyArr, timeArr, ans;
    static List<Integer>[] list;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());

        topologyArr = new int[N+1]; // 진입차수
        timeArr = new int[N+1]; // 건물 건설 시간
        ans = new int[N+1]; // 정답 배열
        list = new ArrayList[N+1]; // 선행 건설 건물정보

        for(int i = 1 ; i <= N ; i ++)
            list[i] = new ArrayList<>();

        for(int i = 1 ; i <= N ; i ++){
            st = new StringTokenizer(br.readLine());
            timeArr[i] = Integer.parseInt(st.nextToken());

            while(true){
                int num = Integer.parseInt(st.nextToken());

                if(num == -1) break;

                // list[num]의 인자들은 num 번호의 건물을 선행해야 함
                list[num].add(i);

                // 진입차수 증가
                topologyArr[i] ++;
            }
        }

        topologySort();

        for(int i = 1 ; i <= N ; i ++)
            sb.append(ans[i] + timeArr[i]).append("\n");

        System.out.print(sb);
    }

    private static void topologySort() {
        Queue<Integer> q = new ArrayDeque<>();

        for(int i = 1 ; i <= N ; i ++)
            if(topologyArr[i] == 0) q.offer(i);

        while(!q.isEmpty()){
            int cur = q.poll();

            for(int next: list[cur]){
               ans[next] = Math.max(ans[next], ans[cur] + timeArr[cur]);
               if(--topologyArr[next] == 0) q.offer(next);
            }
        }
    }
}