[BOJ/백준][JAVA] 2056 - 작업

[문제]

2056번: 작업

 

📒 문제

 

수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다.

몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해 반드시 먼저 완료되어야 할 작업들이 있다. 이 작업들은 번호가 아주 예쁘게 매겨져 있어서, K번 작업에 대해 선행 관계에 있는(즉, K번 작업을 시작하기 전에 반드시 먼저 완료되어야 하는) 작업들의 번호는 모두 1 이상 (K-1) 이하이다. 작업들 중에는, 그것에 대해 선행 관계에 있는 작업이 하나도 없는 작업이 반드시 하나 이상 존재한다. (1번 작업이 항상 그러하다)

모든 작업을 완료하기 위해 필요한 최소 시간을 구하여라. 물론, 서로 선행 관계가 없는 작업들은 동시에 수행 가능하다.

 

📒 해결방법

예제를 먼저 분석하면 알고리즘을 알 수 있다.

7	// N개
5	0
1	1	1
3	1	2
6	1	1
1	2	2	4
8	2	2	4
4	3	3	5	6
작업에 걸리는 시간	선행관계 작업의 개수	선행관계 작업번호	선행관계 작업번호	선행관계 작업번호

즉, 앞선 순서가 있고 그 순서를 행해야 다음 순서로 넘어갈 수 있는 문제이기 때문에 조건을 만족하며 일직선상을 그릴 때 떠올려야 하는 위상 정렬로 문제를 풀 수 있다.

위상 정렬을 구현하는 방식은 ① Stack ② Queue로 구현할 수 있다. 

 

💡 위상정렬 구현 방법

1. 진입 차수가 0인 정점을 Queue에 삽입한다.
   

   for (int i = 1; i < N + 1; i++) {
               sum[i] = time[i];
               if (indegree[i] == 0) {
                   q.offer(i);
               }
           }​

2. Queue에서 원소를 꺼내 연결된 모든 간선을 제거한다
3. 간선 제거 이후에 진입차수가 0이 된것을 다시 Queue에 삽입한다.
   

    while (!q.isEmpty()) {
               int value = q.poll();
   
               for (int i : graph.get(value)) {
                   sum[i] = Math.max(sum[i], sum[value] + time[i]);
   
                   indegree[i]--;
                   if (indegree[i] == 0) {
                       q.offer(i);
                   }
               }
           }​

4. Queue가 빌때까지 2-3번을 반복하다가 Queue가 비었을 때 꺼낸 순서가 위상 정렬의 결과이다

 

📒 전체 소스코드

package BOJ.Graph;

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

public class boj2056_Work {
    static int N;
    static ArrayList<ArrayList<Integer>> graph;
    static int[] indegree;
    static int[] time;
    static int max;

    /**
     * 위상정렬
     * 
     * @param args
     * @throws Exception
     */
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;

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

        for (int i = 0; i < N + 1; i++) {
            graph.add(new ArrayList<>());
        }

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

        for (int i = 1; i < N + 1; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            time[i] = Integer.parseInt(st.nextToken());

            int count = Integer.parseInt(st.nextToken());
            for (int j = 0; j < count; j++) {
                int value = Integer.parseInt(st.nextToken());
                graph.get(value).add(i);

                indegree[i]++;
            }
        }

        indegreeSort();

        System.out.println(max);
    }

    static void indegreeSort() {
        Queue<Integer> q = new LinkedList<>();
        int[] sum = new int[N + 1];

        for (int i = 1; i < N + 1; i++) {
            sum[i] = time[i];
            if (indegree[i] == 0) {
                q.offer(i);
            }
        }

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

            for (int i : graph.get(value)) {
                sum[i] = Math.max(sum[i], sum[value] + time[i]);

                indegree[i]--;
                if (indegree[i] == 0) {
                    q.offer(i);
                }
            }
        }

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

 

📒 리뷰

내 제출

 

---

사실 위상정렬 문제를 얼마 전에 풀어서 좀 더 빨리 떠올렸던 것 같습니다.

그때 문제를 풀 때에는 완벽히 이해가 안돼서 올릴 수 없었지만 이번 문제를 풀면서 더 이해가 된 것 같아서 올렸습니다!! 😚😚😚😚😚😚😚