[백준] 1005 ACM 크래프트 -JAVA

1005번: ACM Craft (acmicpc.net)

1005번: ACM Craft

생각보다 오래 걸린 문제... 처음에 잘못 접근을 해 애 먹었다.

 

풀이

알고리즘 파악

 

위상정렬+ DP 

 

처음에 무턱대고 BFS로 접근하였다... 단순히 이전 건설 시간의 최댓값만 총 건설시간에 더하였는데 모든 정점이 서로 연결된 케이스를 풀 수가 없었다...   

 

구현

 

문제의 핵심은 결국

내 건물의 까지의 총 건설시간 = (이전 테크 건물들의 총 건설시간 중 최댓값) + (내 건설시간)

이라고 생각했다. 

 

그래서 문제를 DP로 접근하였는데, 이전 테크의 건물들이 존재하는지 요소를 파악하기 위해 위상정렬의 요소를 사용하였다. 

indegree[idx] ==0 , 즉 이전 테크의 건물들이 없을시 건설시간을 Return 하도록 하였다.

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
	static int t,n,k;
	static int[]d,indegree,dp;
	static ArrayList<ArrayList<Integer>> list;
    public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
    	 BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	 BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    	 StringBuilder sb = new StringBuilder();
    	 t = Integer.parseInt(br.readLine());
    	 
    	 for(int i=0; i<t; i++)
    	 {
    		 StringTokenizer st = new StringTokenizer(br.readLine()," ");
    		 n = Integer.parseInt(st.nextToken());
    		 k = Integer.parseInt(st.nextToken());
    		 
    		 d = new int[n+1];//시간
    		 dp = new int[n+1];
    		 indegree = new int[n+1];
    		 Arrays.fill(dp, -1);
    		 st = new StringTokenizer(br.readLine()," ");
    		 for(int j=1; j<=n; j++) d[j] = Integer.parseInt(st.nextToken()); //1부터 시작
    		 
    		 list = new ArrayList<ArrayList<Integer>>();
    		 
    		 for(int j=0; j<=n; j++) list.add(new ArrayList<>());
    		 for(int j=0; j<k; j++)
    		 {
    			 st = new StringTokenizer(br.readLine()," ");
    			 int begin = Integer.parseInt(st.nextToken());
    			 int end = Integer.parseInt(st.nextToken());
    			 indegree[end]++;
    			 list.get(end).add(begin);
    		 }
    		 int des = Integer.parseInt(br.readLine());
    		 sb.append(Integer.toString(DP(des))+"\n");

    	 } 
    	 bw.write(sb.toString());
         bw.flush();
         bw.close();
         br.close();
    	 
	}
    
    static int DP(int idx) 
    {
    	if(dp[idx]>-1) return dp[idx]; 
    	if(indegree[idx]<=0) return dp[idx]=d[idx];
    	
        ArrayList<Integer> cur = list.get(idx);
    	
    	for(int i=0; i<cur.size(); i++)
    	{
    		int num = cur.get(i);
    		indegree[idx]--; //뒤 없애기
    	    dp[idx] = Math.max(dp[idx], DP(num));
    	}
    	return dp[idx]+=d[idx];
    }
  
}