[BOJ/GoldIV] 2056. 작업 - JAVA 자바

2056번: 작업

• 592ms
• 위상정렬

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

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

큐를 이용한 위상 정렬 알고리즘

1. 진입차수가 0인 모든 노드를 큐에 넣는다.
2. 큐가 빌 때까지 다음의 과정 반복
   1. 큐에서 원소를 꺼내 해당 노드에서 나가는 간선을 그래프에서 제거
   2. 진입차수가 0이 된 노드를 큐에 넣기

⇒ 결과적으로 각 노드가 큐에 들어온 순서가 위상 정렬을 수행한 결과와 같다.

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

public class Main {
    static int n;
    static int[] indegree;
    static Node[] graph;

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

        public Node(int time) {
            this.time = time;
            list = new ArrayList<>();
        }

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

    }

    public static int topologySort() {
        int time = 0;
        PriorityQueue<Node> pq = new PriorityQueue<Node>();

        for (int i = 1; i <= n; i++) {
            if (indegree[i] == 0)
                pq.offer(graph[i]);
        }

        while (!pq.isEmpty()) {
            Node now = pq.poll();
            time = now.time;

            for (int i = 0; i < now.list.size(); i++) {
                int work = now.list.get(i);
                indegree[work]--;        // 진입차수-1

                if (indegree[work] == 0) {
                    graph[work].time += now.time;
                    pq.offer(graph[work]);
                }
            }
        }
        return time;

    }

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

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

        indegree = new int[n + 1];
        graph = new Node[n + 1];

        // 작업에 걸리는 시간과 선행 관계
        for (int i = 1; i <= n; i++) {
            st = new StringTokenizer(br.readLine());

            graph[i] = new Node(Integer.parseInt(st.nextToken()));

            int tmp = Integer.parseInt(st.nextToken());
            for (int j = 0; j < tmp; j++) {
                graph[Integer.parseInt(st.nextToken())].list.add(i);
                indegree[i]++; // 진입차수+1
            }
        }

        int result = topologySort();
        System.out.println(result);
    }
}