[백준] 2056번 : 작업 - 자바(Java)

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

2056번: 작업

 

문제 해석

수행해야 할 작업이 10000개 주어집니다.

작업들 사이에서는 선행 관계가 존재합니다.

K번 작업에 대해 선행 관계에 있는 작업들은 모두 1 이상 K-1 이하입니다.

선행 관계에 있는 작업이 하나도 없는 작업이 반드시 하나 이상 존재합니다. (1번 작업이 항상 그렇다)

작업들은 동시에도 수행이 가능합니다.

모든 작업을 완료하기 위한 필요한 최소 시간을 구하세요

 

문제 풀이 전 설계

DP와 위상 정렬로 풀이하는 방법을 공부하고자 해당 방법으로 풀이해보려고 합니다.

 

DP 풀이 같은 경우에는 K번 작업에 대해 선행 관계에 있는 작업들이 모두 1 이상 K-1 이하이기 때문에 Bottom Up으로 풀이가 가능합니다.

 

위상 정렬은 작업문제처럼 선행관계로 구성되었을 때 자주 사용됩니다.

 

위상정렬은 indegree 배열을 사용하여 구현할 수 있습니다.

indegree 배열은 해당 노드를 가리키는 간선 개수를 담고 있는 배열입니다.

 

다음 그림을 보면 노드의 하단에 indegree가 적혀있습니다.

https://bcp0109.tistory.com/21

이렇게 indegree 배열을 구성한 후에는 indegree가 0인 노드로부터 출발하여 이동합니다.

그리고 해당 노드가 가는 길에는 indegree가 1씩 감소하게 됩니다.

 

즉 1번 노드에서 한번 출발하면 다음과 같은 그림이 구성됩니다.

https://bcp0109.tistory.com/21

해당 작업을 큐가 빌 때까지 하면 Result에는 위상 정렬된 값이 들어가게 됩니다.

 

 

DP코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main_2056_작업_DP {

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

        int N = Integer.parseInt(br.readLine());
        int[] dp = new int[N + 1]; // 각각의 작업을 수행하는 데 걸리는 시간

        int ans = 0;
        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            int time = Integer.parseInt(st.nextToken());
            int num = Integer.parseInt(st.nextToken());

	//처음에는 time으로 설정
            dp[i] = time;

            for (int j = 0; j < num; j++) {
                int temp = Integer.parseInt(st.nextToken());

                // 가장 긴 수행 시간으로 설정해야 함.
                dp[i] = Math.max(dp[i], dp[temp] + time);
            }

            ans = Math.max(ans, dp[i]);
        }
        System.out.println(ans);

    }

}

 

위상정렬 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

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

        int N = Integer.parseInt(br.readLine());
        ArrayList<ArrayList<Integer>> a = new ArrayList<>();

        for (int i = 0; i <= N; i++) {
            a.add(new ArrayList<>());
        }
        //인접그래프 생성

        int[] indegree = new int[N + 1];
        int[] time = new int[N + 1];

        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());

            time[i] = Integer.parseInt(st.nextToken());

            int num = Integer.parseInt(st.nextToken());
            for (int j = 0; j < num; j++) {
                int temp = Integer.parseInt(st.nextToken());
                a.get(temp).add(i);
                indegree[i]++;
            }
        }

        System.out.println(topologicalSort(N, a, indegree, time));

    }

    // 위상 정렬
    public static int topologicalSort(int N, ArrayList<ArrayList<Integer>> a, int[] indegree, int[] time) {
        Queue<Integer> q = new LinkedList<>();

        int[] result = new int[N + 1]; // 각각의 작업을 수행하는 데 걸리는 시간
        for (int i = 1; i <= N; i++) {
            result[i] = time[i];

            // indegree가 0인 작업을 큐에 넣음.
            if (indegree[i] == 0) {
                q.offer(i);
            }
        }

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

            for (int next : a.get(now)) {
                indegree[next]--;

                result[next] = Math.max(result[next], result[now] + time[next]);

                // 새롭게 indegree가 0이 된 작업을 큐에 넣음.
                if (indegree[next] == 0) {
                    q.offer(next);
                }
            }
        }

        int ans = 0;
        for (int i = 1; i <= N; i++) {
            ans = Math.max(ans, result[i]);
        }

        return ans;
    }

}

 

출처

https://bcp0109.tistory.com/21

위상정렬 Topological Sort (Java)

https://steady-coding.tistory.com/182

[BOJ] 백준 2056번 : 작업 (JAVA)