아이디어

• 위상정렬 알고리즘을 사용한다. 단, 현재까지의 건설 시간이 짧은 순으로 탐색해야 하므로 PQ를 사용한다.
  • 위상 정렬 알고리즘:
    • 각 노드의 진입 차수를 기록해 놓는다 (indeg)
    • 진입차수가 0인 노드를 큐에 넣고 시작한다.
      • 여기서는 현재까지의 건설 시간 정보도 함께 PQ에 넣는다.
    • 큐에서 노드를 가져와 인접한 노드들의 진입 차수를 1씩 낮춘다. (연결을 끊는다.)
    • 진입차수가 0이 된 노드를 큐에 넣는다.
    • 큐가 빌 때까지 반복한다.
      • 여기서는 노드 W를 찾으면 현재까지의 건설 시간을 출력하고 다음 TC로 넘어간다.

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
	static BufferedReader rd = new BufferedReader(new InputStreamReader(System.in));
	static StringBuilder sb = new StringBuilder();
	static StringTokenizer tk = null;

	static int T, N, K, W;
	static int[] D;
	static List<List<Integer>> graph = new ArrayList<>();
	static int[] indeg;

	static PriorityQueue<Building> q = new PriorityQueue<>();
	
	public static void main(String[] args) throws Exception {
		T = Integer.parseInt(rd.readLine());
		T_LOOP: for (int t=1; t<=T; t++) {
			// input
			tk = new StringTokenizer(rd.readLine());
			N = Integer.parseInt(tk.nextToken());
			K = Integer.parseInt(tk.nextToken());
			
			D = new int[N+1];
			tk = new StringTokenizer(rd.readLine());
			for (int i=1; i<=N; i++) {
				D[i] = Integer.parseInt(tk.nextToken());
			}
			
			graph.clear();
			for (int i=0; i<=N; i++) {
				graph.add(new ArrayList<>());
			}
			indeg = new int[N+1];
			for (int i=0; i<K; i++) {
				tk = new StringTokenizer(rd.readLine());
				int X = Integer.parseInt(tk.nextToken());
				int Y = Integer.parseInt(tk.nextToken());
				graph.get(X).add(Y);
				indeg[Y]++;
			}
			
			W = Integer.parseInt(rd.readLine());
			
			// 진입차수 0인 노드 q에 넣기
			q.clear();
			for (int i=1; i<=N; i++) {
				if (indeg[i] == 0) q.offer(new Building(i, D[i]));
			}
			
			// 위상정렬
			while (!q.isEmpty()) {
				Building bdg = q.poll();

				if (bdg.no == W) {
					sb.append(bdg.time).append('\n');
					continue T_LOOP;
				}
				
				for (int n: graph.get(bdg.no)) {
					indeg[n]--;
					if (indeg[n] == 0) q.offer(new Building(n, bdg.time + D[n]));
				}
			}
		}
		
		System.out.println(sb);
	}
	
	static class Building implements Comparable<Building>{
		int no, time;
		Building(int no, int time) {
			this.no = no;
			this.time = time;
		}
		@Override
		public int compareTo(Building o) {
			return Integer.compare(this.time, o.time);
		}
	}
}

메모리 및 시간

• 메모리: 242212 KB
• 시간: 784 ms

리뷰

• 배열이 아닌 선행 노드에 이전 데이터를 저장하는 방식이므로 일단 DP긴 하다.