[백준] 2056번 작업

문제 설명

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

문제 풀이

• 위상 정렬을 이용하였다.
• 사이클이 없는 방향 그래프이므로 사이클 탐지 로직은 넣지 않았다.
• 위상 정렬을 큐를 이용하여 구현하되 degree가 0일 때 큐에 넣을 때 이전 작업 중 가장 늦게 끝나는 시점을 기준으로 넣기 위해 우선순위큐를 이용해 작은 시간부터 처리하도록 구현하였다.

소스 코드 (JAVA)

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

public class Main {
    public static BufferedReader br;
    public static BufferedWriter bw;
    public static int N;
    public static int[] inDeg;
    public static int[] time;
    public static ArrayList<ArrayList<Integer>> edge = new ArrayList<>();

    public static class Point implements Comparable<Point>{
        int n, t;
        public Point(int n, int t) {
            this.n = n;
            this.t = t;
        }
        @Override
        public int compareTo(Point o) {
            if (this.t > o.t) return 1;
            else return -1;
        }
    }

    public static int solve() {
        PriorityQueue<Point> q = new PriorityQueue<>();
        int result = 0;
        for (int i = 1; i <= N; i++)
            if (inDeg[i] == 0) q.add(new Point(i, time[i]));
        while(!q.isEmpty()) {
            Point cur = q.poll();
            result = Math.max(result, cur.t);
            for (int i = 0; i < edge.get(cur.n).size(); i++) {
                int y = edge.get(cur.n).get(i);
                if (--inDeg[y] == 0)
                    q.add(new Point(y, cur.t + time[y]));
            }
        }
        return result;
    }

    public static void input() throws IOException {
        N = Integer.parseInt(br.readLine());
        //초기화
        inDeg = new int[N+1];
        time = new int[N+1];
        for (int i = 0; i <= N; i++)
            edge.add(new ArrayList<>());
        //
        for (int i = 1; i <= N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            time[i] = Integer.parseInt(st.nextToken());
            inDeg[i] = Integer.parseInt(st.nextToken());
            for (int j = 0; j < inDeg[i]; j++)
                edge.get(Integer.parseInt(st.nextToken())).add(i);
        }
    }

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
        input();
        bw.write(solve() + "\n");
        bw.flush();
        bw.close();
        bw.close();
    }
}