1005번 ACM Craft G3

 문제가 꽤나 길다.

 

간단하게 말하자면 해당 건물을 올리기 위해 먼저 다른 건물을 올려야 한다는 것이다.

 

하지만 여기서 특기할 점이 있다면 1번 건물을 짓고 동시에 2번과 3번 건물을 짓기 시작할 수 있다는 것이다.

 

따라서 4번 건물을 짓기 위해 필요한 시간은 1번 건물 10초 + 2번 건물 1초 + 3번 건물 100초 + 4번 건물 10초로 121초

 

가 아니라

 

1번 건물 10초 + (동시에 짓는 건물 중 오래걸리는 시간(2번, 3번))100초 + 4번 건물 10초로 120초이다. 

 

이런 개념을 가지고 가면 간단하게 위상 정렬로 풀린다.

 

다른 건 다 위상정렬과 비슷하나 추가적으로 필요한 것은 

 

최소의 시간을 기록할 DP 배열과 건물짓는데 걸리는 시간을 비교할 방법이다.

 

DP[1] (1번째 값) 은 건물1의 건축 시간으로 초기화하고,

 

Queue를 뽑으면서 dp[i]를 갱신한다.

 

while(!q.isEmpty()){
	int tmp = q.poll();
    order[tmp]--;
    for(Node n: list[tmp]){
    	order[n.v]--;
        if(dp[n.v]<dp[tmp]+arr[n.v])
        	dp[n.v]=dp[tmp]+arr[n.v];
        if(order[n.v]==0)
        	q.add(n.v);
    }
}

 

 여기서는 다음 건물과 해당 건물을 짓기 위한 시간을 저장할 수 있는 Node 클래스를 만들었다

 

class Node{
	int v;
    int w;
    Node(int v,int w){
    	this.v=v;
        this.w=w;
    }
    
}

또 진입 차수를 저장하는 order 배열을 만들어 진입차수를 관리했다.

 

그 후 진입 차수가 0인 노드를 큐에 넣고 

 

큐가 공백상태가 될 때까지 해당 구문을 반복했다.

 

이때 dp 배열에 입력할 때는 진입 정점에서 진출 정점까지 걸리는 시간,

 

즉 해당 건물을 준공하고 다음 건물을 지을 때 걸리는 시간이 최대인 것을 넣는다.

 

이는 2번과 3번 건물에서 4번 건물로 넘어갈 때와 같은 상황에서 

 

동시에 짓는다는 것을 가정할 때 가장 오래걸리는 시간을 입력하는 것과 같다.

 

2번이 아무리 빨리 끝나도 결국 4번 건물을 짓기 위해서는 

 

3번 건물을 다 지어야 하기 때문이다.

 

해당 건물 빌드로 진입하기 위해 그 전 빌드에서 건축시간이 가장 오래걸리는 것을 입력하는 것이다.

 

이렇게 작성하면 문제가 풀린다. 

 

다음은 문제풀이 코드 전체이다.

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	static int n, k;
	static int []arr;
	static int []order;
	static int [] dp;
	static LinkedList<Node>[] list;
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int T=Integer.parseInt(br.readLine());
		for(int t=0;t<T;t++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			n=Integer.parseInt(st.nextToken());
			k=Integer.parseInt(st.nextToken());
			arr=new int [n+1];
			order=new int [n+1];
			list=new LinkedList[n+1];
			dp=new int [n+1];
			for(int i=0;i<n+1;i++) {
				list[i]=new LinkedList<>();
			}
			st=new StringTokenizer(br.readLine());
			for(int i=1;i<=n;i++) {
				arr[i]=Integer.parseInt(st.nextToken());
			}
			for(int i=0;i<k;i++) {
				st=new StringTokenizer(br.readLine());
				int a= Integer.parseInt(st.nextToken());
				int b=Integer.parseInt(st.nextToken());
				list[a].add(new Node(b,arr[b]));
				order[b]++;
			}
			int w=Integer.parseInt(br.readLine());
			Queue<Integer> q = new LinkedList<>();
			for(int i=1;i<=n;i++) {
				if(order[i]==0) {
					q.add(i);
					dp[i]=arr[i];
				}
				
			}
			while(!q.isEmpty()) {
				int tmp=q.poll();
				order[tmp]--;
				for(Node n:list[tmp]) {
					order[n.v]--;

					if(dp[n.v]<dp[tmp]+arr[n.v])
						dp[n.v]=dp[tmp]+arr[n.v];
					if(order[n.v]==0) {
						q.add(n.v);
					
					}
				}
			}
			bw.write(String.valueOf(dp[w]));
			bw.newLine();
		}

		bw.close();
		br.close();
		
	}
	
}
class Node{
	int v;
	int w;
	Node(int v,int w){
		this.v=v;
		this.w=w;
	}
}