[BOJ 1005] ACM Craft (Java)

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

1005번: ACM Craft

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

public class Main_BOJ_1005 {
	static class Building implements Comparable<Building>{
		int id, cost;	
		public Building(int id, int cost) {
			this.id = id;
			this.cost = cost;
		}
		@Override
		public int compareTo(Building b) {
/*			if (this.level==b.level) return this.cost-b.cost;
			return this.level-b.level;*/
			return this.cost-b.cost;
		}
	}
	static int T, N, K, W;
	static int[] times;
	static int[] inDegrees;
	static ArrayList<ArrayList<Integer>> adjList;
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=null;
		T=Integer.parseInt(br.readLine());
		for (int t=1; t<=T; t++) {
			st=new StringTokenizer(br.readLine());
			N=Integer.parseInt(st.nextToken());
			K=Integer.parseInt(st.nextToken());
			times=new int[N+1];
			inDegrees=new int[N+1];
			adjList=new ArrayList<>();
			for (int i=0; i<N+1; i++) {
				adjList.add(new ArrayList<Integer>());
			}
			st=new StringTokenizer(br.readLine());
			for (int i=1; i<=N; i++) {
				times[i]=Integer.parseInt(st.nextToken());
			}
			for (int i=0; i<K; i++) {
				st=new StringTokenizer(br.readLine());
				int X=Integer.parseInt(st.nextToken());
				int Y=Integer.parseInt(st.nextToken());
				adjList.get(X).add(Y);
				inDegrees[Y]++;
			}
			W=Integer.parseInt(br.readLine());
			System.out.println(sol());
		}
	}
	
	private static int sol() {
		PriorityQueue<Building> pq=new PriorityQueue<>();
		for (int i=1; i<=N; i++) {
			if (inDegrees[i]==0) pq.add(new Building(i, times[i]));
		}
		while (!pq.isEmpty()) {
			Building b=pq.poll();
			if (b.id==W) return b.cost;
			for (int i=0; i<adjList.get(b.id).size(); i++) {
				int neighbor=adjList.get(b.id).get(i);
				inDegrees[neighbor]--;
				if (inDegrees[neighbor]==0) {
					pq.add(new Building(neighbor, b.cost+times[neighbor]));
				}
			}
		}
		return -1;
	}

}

위상 정렬 문제이다.

 

우선 Building 이라는 클래스를 만들어서, 각 건물의 넘버와 그 건물 짓기까지 걸리는 최소 시간인 cost를 저장하는 필드를 만든다. 비교자를 만들어, priority queue에 넣을 때 가장 짧은 시간이 걸리는 것부터 먼저 튀어나오도록 한다.

 

그 이후에는 위상정렬 방식과 마찬가지로,

inDegree가 0 인 것에 한해 큐에 넣고 W가 나올 경우 cost를 리턴하는 방식이다.

 

항상 시간이 짧은 것부터 먼저 튀어나온다는 특성이 있다.

즉,  목표 건물인 5번 건물을 세우기까지 세워야 하는 건물이 cost가 2가 걸리는 1번, cost가 5인 2번, cost가 7인 3번 이렇게 3개가 있을 때 가장 큰 비용이 드는 3번 건물을 뽑고 나서야 비로소 5번의 indegree가 0이 되기 때문에 3번까지 세우는데 걸리는 비용+5번 세우는데 걸리는 비용을 한 것이 최종 답이 될 것이다.  

 

그런데 사실 이 방식은 뭔가 떠올리기가 쉽지 않은? 방식 같다.. 조금 더 직관적인 방식이 있었다.

다른 분들의 코드를 보니 (https://nanyoungkim.tistory.com/128)

a번 건물과 연결된 다른 건물을 만날 때마다 시간을 최댓값으로 갱신해 주는 방식으로 풀 수 있다. 

즉 max값을 갱신하는 방식과 비슷한 원리인 것이다.