[BOJ] 1005. ACM Craft

위상정렬을 이용한 문제였다.

이 문제는 그림에 주어졌듯이 건물사이의 우선순위가 존재하고 사이클이 생기지 않기때문에 위상정렬을 사용하여 접근하였다. 다만 주의할점은 건설함에 있어 이전것이 다 지어져야하는 시간을 가져가야하기 때문에 시간을 갱신함에 있어 max 값을 처리해주는 것을 생각해야한다.

package algostudy2;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main_bj_1005_ACMCRAFT {
    static int N;
    static int[] indegree;
    static int[][] graph;
    static int[] time;
    static int[] answer;
 
    static Queue<Integer> queue;
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
 
        int T = Integer.parseInt(br.readLine());
 
        for (int tc = 1; tc <= T; tc++) {
            st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            int W = Integer.parseInt(st.nextToken());
 
            init();
 
            st = new StringTokenizer(br.readLine());
            for (int i = 1; i <= N; i++) {
                time[i] = Integer.parseInt(st.nextToken());
            }
 
            for (int w = 0; w < W; w++) {
                st = new StringTokenizer(br.readLine());
                int start = Integer.parseInt(st.nextToken());
                int end = Integer.parseInt(st.nextToken());
 
                indegree[end] += 1;
                graph[start][end] = 1;
            }
 
            topological();
 
            int answerIndex = Integer.parseInt(br.readLine());
 
            System.out.println(answer[answerIndex]);
        }
    }
 
    static void init() {
        graph = new int[N + 1][N + 1];
        time = new int[N + 1];
        indegree = new int[N + 1];
        answer = new int[N + 1];
    }
 
    static void topological() {
        queue = new LinkedList<>();
 
        for (int i = 1; i <= N; i++) {
            if (indegree[i] == 0) {
                queue.offer(i);
                answer[i] = time[i];
            }
        }
 
        while (!queue.isEmpty()) {
            int cur = queue.poll();
 
            for (int i = 1; i <= N; i++) {
                if (graph[cur][i] != 0) {
                    int next = i;
 
                    answer[next] = Math.max(answer[next], answer[cur] + time[next]);
 
                    indegree[next]--;
 
                    if (indegree[next] == 0) {
                        queue.offer(next);
                    }
                }
            }
        }
    }
}