[BOJ]1005_ACM Craft_Java

--문제--

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

1005번: ACM Craft

--문제접근--

문제를 읽어보면 위상정렬을 사용하면 되는 문제란 것을 볼 수 있다.

그래서 저는 위상정렬을 사용하기 위하여

하나의 건물을 짓기까지 총 걸리는 시간 을 구해주기 위한 value

연결되어있는 것을 확인해주기 위한 배열 ADJ배열

건물을 건설할 수 있는지 확인하기 위한 indgeree 배열

시간이 얼마나 걸리는지 확인하기 위한 timetable배열

그리고 마지막으로 Queue를 통해 indegree0인것을 하나씩 넣어줄것입니다.

쉽게말해

맨처음 indegree0인것을 한번 Queue에 넣어주고 시작을하여 계속 최신화과정을 거친다음 마지막 value[목표]를 출력하면 답이 나온다고생각하였습니다.

package 백준문제풀이;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class BOJ_1005 {
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int TC=sc.nextInt();
		for(int t=0;t<TC;t++) {
			int N=sc.nextInt();
			int M=sc.nextInt();
			int[][] adj=new int[N+1][N+1];
			int[] timetable=new int[N+1];
			int[] indegree=new int[N+1];
			int[] value=new int[N+1];
			for(int i=1;i<=N;i++) {
				timetable[i]=sc.nextInt();
			}
			for(int i=0;i<M;i++) {
				int from=sc.nextInt();
				int to=sc.nextInt();
				adj[from][to]=1;
				indegree[to]++;
			}
			int goal=sc.nextInt();//목표지점
			int ans=0;
			Queue<Integer> queue=new LinkedList<Integer>();
			for(int i=1;i<N+1;i++) {
				if(indegree[i]==0) {
					queue.add(i);
					value[i]=timetable[i];
				}
			}
			while(!queue.isEmpty()) {
				int curr=queue.poll();
				for(int i=1;i<=N;i++) {
					if(adj[curr][i]==1) {
						indegree[i]-=1;
						value[i]=Math.max(value[i], value[curr]+timetable[i]);
						if(indegree[i]==0) {
							queue.add(i);
						}
					}
				}
			}
			System.out.println(value[goal]);
			
		}
	}

}