[백준] 1516번 게임개발

문제 설명

• https://www.acmicpc.net/problem/1516
• Gold 3
• 소요 시간 : 16분

문제 풀이

• 위상 정렬을 이용하여 풀이하였다.
• 위상 정렬을 이용하되 특정 노드의 최대 시작 가능 시간(이전 건물 중 가장 마지막으로 건설을 끝낸 시간)을 배열로 두어 갱신해주며 진행하고 큐에서 뺄 때 해당 시간 + 건설 시간을 결과로 넣어주었다.

소스 코드 (JAVA)

import java.io.*;
import java.util.*;
class Main {

    static BufferedWriter bw;
    static BufferedReader br;

    static int N;
    static int[] start;    // 각 건물의 최대 시작 가능 시간
    static int[] inDegree; // 각 건물의 진입 차수
    static int[] delay;    // 각 건물의 건설 시간
    static List<List<Integer>> map = new ArrayList<>();

    // 위상 정렬 알고리즘 진행
    static void solve() throws IOException {
        int[] result = new int[N+1];
        Queue<Integer> q = new ArrayDeque<>();
        for (int i = 1; i <= N; i++) {
            if (inDegree[i] == 0)
                q.add(i);
        }

        while(!q.isEmpty()) {
            Integer cur = q.poll();
            result[cur] = start[cur] + delay[cur];

            for (int i = 0; i < map.get(cur).size(); i++) {
                int next = map.get(cur).get(i);
                start[next] = Math.max(start[next], start[cur] + delay[cur]);
                if (--inDegree[next] == 0)
                    q.add(next);
            }
        }

        for (int i = 1; i <= N; i++)
            bw.write(result[i] + "\n");
        bw.flush();
    }

    static void input() throws IOException {
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
        br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        start = new int[N+1];
        inDegree = new int[N+1];
        delay = new int[N+1];
        for (int i = 0; i <= N; i++)
            map.add(new ArrayList<>());
        for (int i = 1; i <= N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            delay[i] = Integer.parseInt(st.nextToken());
            while(true) {
                int cur = Integer.parseInt(st.nextToken());
                if (cur == -1) break;
                inDegree[i]++;
                map.get(cur).add(i);
            }
        }
    }

    public static void main(String[] args) throws IOException {
        input();
        solve();
    }
}

/**
 * 게임 개발 (18:12)
 *
 * - N : 건물의 종류 수 (<=500)
 * - 각 건물이 완성되기까지 걸리는 최소 시간
 *
 * - 위상 정렬
 * - 각 건물의 최대 시작 가능 시간을 갱신해가며 진행
 *
 * N
 * 건물 건설 시간, 선행 건물.. , -1
 */