[백준]1005: ACM Craft - JAVA

[백준]1005: ACM Craft

www.acmicpc.net/problem/1005

1005번: ACM Craft

풀이

위상 정렬을 하면서 cost값을 계산해 주어야 하는 문제이다. 위상정렬 알고리즘에 따라 순서를 정하고, 순서가 결정될 때마다 cost값을 계산해 준다. 

 

이때 중요한 점은 문제에서는 최소 비용을 구하라고 하였지만, 결국에 따지고 보면 최대 cost를 구해야 한다는 점이다.

 

위의 경우에 4를 건설하는 건설시간은 120초가 된다. 그 이유는 문제의 조건에 따라 4를 위해 2, 3을 모두 건설해야 하고 이때 3의 건설시간이 100초가 걸리므로 2는 3을 기다려야 한다. 즉 더 오래 걸리는 시간을 기준으로 생각해 주어야 한다.

 

이를 위해 buildCost배열을 만들어 주어서 현재 건물을 건설하는데 가장 오래 걸리는 건설 시간을 저장해 주도록 하였고 건설해야할 건물(w)에 해당하는 buildCost[w]를 출력해 주면 된다.

 

코드

import java.util.*;
 
public class Main {    
 
    static int n, w;
    static ArrayList<Integer>[] list; //연결 간선 정보
    static int[] building; //빌딩 짓는 비용 정보
    static int[] indegree;
    static int[] buildCost; //각 위치까지 빌딩을 짓는 비용의 최대값을 저장한다.
    
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
 
        int t = scan.nextInt();
        for(int i = 0; i < t; i++) {
            n = scan.nextInt();
            int k = scan.nextInt();
            
            building = new int[n + 1];
            list = new ArrayList[n + 1];
            for(int j = 1; j <= n; j++) {
                building[j] = scan.nextInt();
                list[j] = new ArrayList<>();
            }
            
            indegree = new int[n + 1];
            for(int j = 0; j < k; j++) {
                int s = scan.nextInt();
                int e = scan.nextInt();
                list[s].add(e); 
                indegree[e]++;
            }
            w = scan.nextInt(); //건설해야 할 건물의 번호
            
            buildCost = new int[n + 1]; 
            topologySort();
            System.out.println(buildCost[w]);
        }
    }
    
    public static void topologySort() {
        Queue<Integer> q = new LinkedList<>();
        for(int i = 1; i < indegree.length; i++) {
            if(indegree[i] == 0) {
                buildCost[i] = building[i];
                q.offer(i);
            }
        }
        
        while(!q.isEmpty()) {
            int current = q.poll();
            
            for(int i = 0; i < list[current].size(); i++) {
                int next = list[current].get(i);
                buildCost[next] = Math.max(buildCost[current] + building[next], buildCost[next]);
                indegree[next]--;
                if(indegree[next] == 0) q.offer(next);
            }
        }
    }
}