[BOJ/GoldIII] 1516. 게임 개발 - JAVA 자바

 

1516번: 게임 개발

- 208ms

- 위상정렬

선행관계 + 사이클이 없는 방향그래프 ➜ 위상정렬 !!

어떤 작업을 수행하기 전 반드시 선행되어야 하는 작업이 존재한다. 작업의 시간과 선행관계가 주어졌을 때, 모든 작업을 완료하기 위해 필요한 최소시간을 구하는 문제이다. ( 비슷한 문제 : BOJ 작업 )

 

진입차수 즉, 선행관계가 없거나 모두 완료되어 시작해도 되는 작업들을 우선순위 큐에 넣는다.

 

# 소스코드

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

public class Main {

    static int n;
    static int[] indegree, result;
    static Node[] graph;

    static class Node implements Comparable<Node> {
        int index;
        int time;
        ArrayList<Integer> list;

        public Node() {
            list = new ArrayList<>();
        }

        @Override
        public int compareTo(Node o) {
            return this.time - o.time;
        }
    }

    public static void topologySort() {
        PriorityQueue<Node> pq = new PriorityQueue<>();

        for (int i = 1; i <= n; i++) {
            if (indegree[i] == 0) // 진입차수가 0인 노드들은 큐에 넣기
                pq.offer(graph[i]);
        }

        while (!pq.isEmpty()) {
            Node now = pq.poll();
            result[now.index] = now.time; // 작업 완료

            for (int i = 0; i < now.list.size(); i++) {
                int work = now.list.get(i);
                indegree[work]--; // now가 선행작업인 노드들의 진입차수 - 1 

                if (indegree[work] == 0) { // 선행작업이 모두 끝난 노드들은 큐에 추가
                    graph[work].time += now.time;
                    pq.offer(graph[work]);
                }
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();

        n = Integer.parseInt(br.readLine());
        indegree = new int[n + 1];
        graph = new Node[n + 1];
        result = new int[n + 1];

        for (int i = 0; i <= n; i++) {
            graph[i] = new Node();
        }

        for (int i = 1; i <= n; i++) {
            st = new StringTokenizer(br.readLine());
            int time = Integer.parseInt(st.nextToken());
            graph[i].index = i;
            graph[i].time = time;
            while (st.hasMoreTokens()) {
                int preWork = Integer.parseInt(st.nextToken());
                if (preWork == -1) break;

                graph[preWork].list.add(i);
                indegree[i]++;
            }
        }
        topologySort();

        for (int i = 1; i <= n; i++) {
            sb.append(result[i]).append('\n');
        }
        System.out.println(sb);
    }

}