[BOJ] 백준 [1005] ACM Craft JAVA

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

1005번: ACM Craft

[문제]

[풀이]

위와 같이 task 를 수행하는 순서가 있는 경우엔 위상정렬로 접근해야 한다.

이 문제에선 건물을 짓는데 있어서 선행조건이 존재하므로 위상정렬을 이용하여 inDegree 를 하나씩 낮춰가면서 진행.

 

A,B 라는 건물을 지어야만 C를 지을수 있을 때

A와 B 건물중에서 더 오래걸리는 건물 기준으로 C까지 짓는데 걸리는 시간이 정해진다.

건물 n을 짓는데 걸리는 시간을 time[n] 이라고하고

n 까지 짓는데 걸리는 이전과정 포함한 총 시간을 buildTime[n] 이라고 하면

 

ex. A 건물에서 접근 시

buildTime[C] => max ( buildTime[C] , buildTime[A] + time[C] )  

 

ex. B 건물에서 접근 시

buildTime[C] => max ( buildTime[C] , buildTime[B] + time[C] )  

 

따라서 점화식은 다음과 같다.

buildTime[next] => max ( buildTime[next] , buildTime[cur] + time[next] )  

 

import java.util.stream.*;
import static java.util.Arrays.*;


import java.util.*;
import java.io.*;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int tc = Integer.parseInt(br.readLine());

        while (tc-->0){
            int[] size = stream(br.readLine().split(" "))
                    .mapToInt(Integer::parseInt).toArray();
            ACM acm = new ACM(size[0]);
            acm.time = stream(("0 "+br.readLine()).split(" "))
                    .mapToInt(Integer::parseInt).toArray(); // 빌드 시간 입력
            for(int i=0;i<size[1];i++){
                int[] edge = stream(br.readLine().split(" "))
                        .mapToInt(Integer::parseInt).toArray();
                acm.roadMap.get(edge[0]).add(edge[1]);
                acm.inDegree[edge[1]]++;
            } // list, inDegree 초기화
            acm.build(Integer.parseInt(br.readLine()));
        }
    }

    static class ACM{

        int n;
        ArrayList<ArrayList<Integer>> roadMap;
        int[] inDegree,buildTime,time;

        public ACM(int n) {
            this.n = n;
            this.roadMap = new ArrayList<>();
            this.inDegree = new int[n+1];
            this.buildTime = new int[n+1];
            for(int i=0;i<=n;i++)
                roadMap.add(new ArrayList<>());
        }
        public int build(int target){

            LinkedList<Integer> q = new LinkedList<>();

            for(int i=1;i<=n;i++){
                if(inDegree[i]==0) {
                    q.add(i);
                    buildTime[i] = time[i]; // inDegree 가 0인 시작지점 빌드시간 초기화
                }
            }

            while (!q.isEmpty()){ // bfs 탐색 시작
                Integer cur = q.poll();
                for (int next : roadMap.get(cur)) {
                    if(--inDegree[next]==0)
                        q.add(next);
                    buildTime[next] = Math.max(buildTime[next],buildTime[cur]+time[next]); // 빌드 시간 갱신
                }
            }
            return buildTime[target];
        }
    }
}