[BOJ] 백준 1005 ACM Craft

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

 Input 

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

 

 Output 

120

39

위상정렬 (Topological sort) 

위상정렬 (Topological sort)

  　

시뮬레이션

▶ 진입차수가 0인 정점의 cost를 answer에 할당

indegree = [0 1 1 2]

answer = [10, 0, 0, 0]

 

 

▶ 정점 ①과 연결된 정점 처리

indegree = [0 0 0 2]

answer = [10, 11, 110, 0]

 

▶ 정점 ②와 연결된 정점 처리

indegree = [0 0 0 1]

answer = [10, 11, 110, 21]

 

 

▶ 정점 ③과 연결된 정점 처리

indegree = [0 0 0 0]

answer =   [10, 11, 110, Max(21, 110+10)]

             =   [10, 11, 110, 120]

 

---

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
 
public class Main {
     
    static ArrayList<ArrayList<Integer>> adList;
    static int N, M;
    static int[] indegree, buildTime, answer;
    static Queue<Integer> queue;
     
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
         
        int T = Integer.parseInt(sc.next());
        while(T-- > 0) {
            // 정점의 개수
            N = Integer.parseInt(sc.next());
            indegree = new int[N+1];
            buildTime = new int[N+1];
                 
            // 인접 리스트로 구현
            adList = new ArrayList<>();
            adList.add(new ArrayList<>());
             
            // 간선의 개수
            M = Integer.parseInt(sc.next());
            // 1~N까지의 각 정점을 리스트에 삽입
            for(int i=1; i<=N; i++) {
                adList.add(new ArrayList<>());
            }
             
            for(int i=1; i<=N; i++) {
                buildTime[i] = Integer.parseInt(sc.next());
            }
            for(int i=1; i<=M; i++) {
                // 해당 건물을 짓기전에 미리 지어져야 하는 건물이 있다면
                int vertex = Integer.parseInt(sc.next());
                int connectedVertex = Integer.parseInt(sc.next());
                 
                adList.get(vertex).add(connectedVertex);
                indegree[connectedVertex]++;
            }
             
            int target = Integer.parseInt(sc.next());
             
            answer = new int[N+1];
            queue = new LinkedList<>();
             
            // 위상정렬
            topological_sort();
            System.out.println(answer[target]);
        }
    }
     
    private static void topological_sort() {
        for(int i=1; i<=N; i++) {
            if(indegree[i] == 0) {
                queue.add(i);
                answer[i] = buildTime[i];
            }
        }
         
        for(int i=1; i<=N; i++) {
            int pre = queue.poll();
            ArrayList<Integer> curNodeList = adList.get(pre);
            // 연결된 지점을 찾는다.
            while(!curNodeList.isEmpty()) {
                int current = curNodeList.remove(0);
                answer[current] = Math.max(answer[pre] + buildTime[current], answer[current]);
                // 진입 차수 갱신
                indegree[current]--;
                if(indegree[current] == 0) {
                    queue.add(current);
                }
            }
        }
    } // end of topological_sort()
}