[백준 1005] ACM Craft (Java) - 위상정렬, 다이나믹 프로그래밍

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

ACM Craft

문제

서기 2012년! 드디어 2년간 수많은 국민들을 기다리게 한 게임 ACM Craft (Association of Construction Manager Craft)가 발매되었다.

이 게임은 지금까지 나온 게임들과는 다르게 ACM크래프트는 다이나믹한 게임 진행을 위해 건물을 짓는 순서가 정해져 있지 않다. 즉, 첫 번째 게임과 두 번째 게임이 건물을 짓는 순서가 다를 수도 있다. 매 게임시작 시 건물을 짓는 순서가 주어진다. 또한 모든 건물은 각각 건설을 시작하여 완성이 될 때까지 Delay가 존재한다.

위의 예시를 보자.

이번 게임에서는 다음과 같이 건설 순서 규칙이 주어졌다. 1번 건물의 건설이 완료된다면 2번과 3번의 건설을 시작할수 있다. (동시에 진행이 가능하다) 그리고 4번 건물을 짓기 위해서는 2번과 3번 건물이 모두 건설 완료되어야지만 4번건물의 건설을 시작할수 있다.

따라서 4번건물의 건설을 완료하기 위해서는 우선 처음 1번 건물을 건설하는데 10초가 소요된다. 그리고 2번 건물과 3번 건물을 동시에 건설하기 시작하면 2번은 1초뒤에 건설이 완료되지만 아직 3번 건물이 완료되지 않았으므로 4번 건물을 건설할 수 없다. 3번 건물이 완성되고 나면 그때 4번 건물을 지을수 있으므로 4번 건물이 완성되기까지는 총 120초가 소요된다.

프로게이머 최백준은 애인과의 데이트 비용을 마련하기 위해 서강대학교배 ACM크래프트 대회에 참가했다! 최백준은 화려한 컨트롤 실력을 가지고 있기 때문에 모든 경기에서 특정 건물만 짓는다면 무조건 게임에서 이길 수 있다. 그러나 매 게임마다 특정건물을 짓기 위한 순서가 달라지므로 최백준은 좌절하고 있었다. 백준이를 위해 특정건물을 가장 빨리 지을 때까지 걸리는 최소시간을 알아내는 프로그램을 작성해주자.

입력

첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부터 N번까지 존재한다) 

둘째 줄에는 각 건물당 건설에 걸리는 시간 D1, D2, ..., DN이 공백을 사이로 주어진다. 셋째 줄부터 K+2줄까지 건설순서 X Y가 주어진다. (이는 건물 X를 지은 다음에 건물 Y를 짓는 것이 가능하다는 의미이다) 

마지막 줄에는 백준이가 승리하기 위해 건설해야 할 건물의 번호 W가 주어진다.

출력

건물 W를 건설완료 하는데 드는 최소 시간을 출력한다. 편의상 건물을 짓는 명령을 내리는 데는 시간이 소요되지 않는다고 가정한다.

건설순서는 모든 건물이 건설 가능하도록 주어진다.

제한

• 2 ≤ N ≤ 1000
• 1 ≤ K ≤ 100,000
• 1 ≤ X, Y, W ≤ N
• 0 ≤ Di ≤ 100,000, Di는 정수

예제 입력 1 복사

2
4 4
10 1 100 10
1 2
1 3
2 4
3 4
4
8 8
10 20 1 5 8 7 1 43
1 2
1 3
2 4
2 5
3 6
5 7
6 7
7 8
7

예제 출력 1 복사

120
39

---

풀이

전체코드

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

public class Main {
    public static void main(String[] args)throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine()); // 테스트 케이스 개수

        // 테스트 시작
        for(int t=0; t<T; t++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            int N = Integer.parseInt(st.nextToken()); // 건물 개수
            int K = Integer.parseInt(st.nextToken()); // 건설순서 규칙개수

            int[] indegree = new int[N+1]; // 진입차수 배열 (건물번호 1번부터 시작)
            Craft[] crafts = new Craft[N+1]; // 건설정보
            int[] spent = new int[N+1]; // i번 건물 짓는데 소요되는 최소시간

            ArrayList<Craft>[] A = new ArrayList[N+1]; // 건물 건설정보 저장 그래프

            // 인접노드 리스트 초기화
            for(int i=1; i<N+1; i++){
                A[i] = new ArrayList<>();
            }

            // 건물 건설정보 입력받기
            st = new StringTokenizer(br.readLine());
            for(int i=1; i<N+1; i++){
                int time = Integer.parseInt(st.nextToken());
                crafts[i] = new Craft(i, time);
            }

            // 건설규칙 정보받기
            for(int i=0; i<K; i++){
                st = new StringTokenizer(br.readLine());
                int first = Integer.parseInt(st.nextToken());
                int second = Integer.parseInt(st.nextToken());

                A[first].add(crafts[second]); // first 건설 후 -> second 건설
                indegree[second]++; // second 건물 진입차수 증가
            }

            // 목표 건물번호
            int target = Integer.parseInt(br.readLine()); // 목표 건물 번호

            // 위상정렬
            Queue<Craft> q = new LinkedList<>();

            // 진입차수 0인 건물 큐에 넣기
            for(int i=1; i<N+1; i++){
                if (indegree[i] == 0){
                    q.offer(crafts[i]);
                }
            }

            while (!q.isEmpty()){
                Craft now = q.poll();
                spent[now.num] += now.time;
                if (now.num == target){
                    System.out.println(spent[now.num]);
                    break;
                }

                for(Craft next : A[now.num]){
                    indegree[next.num]--; // 진입차수 감소
                    spent[next.num] = Math.max(spent[next.num], spent[now.num]);
                    if (indegree[next.num] == 0){
                        q.offer(next);
                    }
                }
            }

        }
    }
}
class Craft{
    int num; // 건물번호
    int time; // 건설 소요시간

    public Craft(int num, int time){
        this.num = num;
        this.time = time;
    }
}

• 위상정렬, 다이나믹 프로그래밍을 활용한 문제
• 푸는데 오백만년 걸린 문제
• 건설 조건
  • 먼저 지어야 하는 건물이 존재함 -> 위상정렬 문제
  • 동시에 짓기도 가능, 특정 건물을 빨리 지을 때까지 걸리는 최소시간 -> 다이나믹 프로그래밍
• 건물의 번호와 건설소요시간을 저장하기 위해 Craft라는 클래스를 정의하였다.
• 건물개수 N, 건설순서 규칙개수 K를 받아서
• 진입차수 배열 indegree, 건설정보를 받을 Craft배열 crafts, n번 건물을 짓는 데 소요되는 최소시간을 담아줄 배열 spent를 N+1 크기로 선언해준다.

crafts : 건물 건설정보 입력받기

            // 건물 건설정보 입력받기
            st = new StringTokenizer(br.readLine());
            for(int i=1; i<N+1; i++){
                int time = Integer.parseInt(st.nextToken());
                crafts[i] = new Craft(i, time);
            }

• 건물을 짓는데 걸리는 소요시간을 한번에(순서대로) 한줄로 주어지므로 crafts 라는 배열을 선언해주었다.
• 번호 순서대로 건설시간을 저장해준다.

A : 건설규칙 입력받기

            // 건설규칙 정보받기
            for(int i=0; i<K; i++){
                st = new StringTokenizer(br.readLine());
                int first = Integer.parseInt(st.nextToken());
                int second = Integer.parseInt(st.nextToken());

                A[first].add(crafts[second]); // first 건설 후 -> second 건설
                indegree[second]++; // second 건물 진입차수 증가
            }

• fist 건물 건설 후 -> second 건물 지어야 하므로
• A[first]에 second Craft를 add해준다.
• second 건물에 선행되어야 하는 건물이 있다는 뜻으로 진입차수를 1증가 시켜준다.

target : 목표 건물번호

// 목표 건물번호
            int target = Integer.parseInt(br.readLine());

• 백준이는 특정 건물번호만 지으면 무조건 이긴다고 했으므로
• target값을 받아서 위상정렬하다가 target값을 만나면 바로 건설소요시간을 출력해주면 된다.

위상정렬

            // 위상정렬
            Queue<Craft> q = new LinkedList<>();

            // 진입차수 0인 건물 큐에 넣기
            for(int i=1; i<N+1; i++){
                if (indegree[i] == 0){
                    q.offer(crafts[i]);
                }
            }

            while (!q.isEmpty()){
                Craft now = q.poll();
                spent[now.num] += now.time;
                if (now.num == target){
                    System.out.println(spent[now.num]);
                    break;
                }

                for(Craft next : A[now.num]){
                    indegree[next.num]--; // 진입차수 감소
                    spent[next.num] = Math.max(spent[next.num], spent[now.num]);
                    if (indegree[next.num] == 0){
                        q.offer(next);
                    }
                }
            }

• 다이나믹 프로그래밍
  • n번째 건물을 짓는데 걸리는 최소시간을 담는 spent를 선언하였다.
  • 만약 건물이 거의 다 지어졌다고 생각하고 다이나믹 프로그래밍 점화식을 생각해보자
    • 예제 1번의 경우 4번 건물의 진입차수는 2이다.
    • 4번 건물을 짓기 위해서는 2,3번 건물이 지어져야 한다.
    • 2번 건물을 짓는데 걸리는 시간은 총 11이다.
    • 3번 건물을 짓는데 걸리는 시간은 총 110이다.
    • 건물은 동시건설이 가능하다. 2,3번이 동시에 지어지기 시작한다고 가정하자
    • 3번 건물을 짓는데 오래걸리므로 110초까지 기다렸다가 4번 건물을 짓기 시작해야 한다.
    • spent[4] = Math.max(spent[20] + 10, spent[40] + 10) 인 것이다.
• Craft를 담는 큐를 선언 후, 진입차수가 0인 Craft를 큐에 넣는다.
• 큐가 빌때까지 아래 동작을 반복수행한다.
  • 큐에서 poll하여 now(Craft)를 뽑는다.
  • spent[now.num]에는 now까지 오기까지의 누적시간이 담겨있다.
  • spent[now.num]에 now.time을 더한다.
  • 만약 now가 target이라면 spent[now.num] 출력후 break한다.
  • now의 인접노드 리스트를 순회하면서 next의 진입차수를 1감소시킨다.
  • spent[next.num], spent[now.num]을 비교해서 최댓값을 spent[next.num]에 넣어준다. 
    • 진입차수를 감소시켰을 때 진입차수가 0이 되면 next를 큐에 넣는다.