[알고리즘] ACM Craft (백준 1005번)

1005번: ACM Craft

 그래프 상으로 본인보다 앞서 있는 건물들이 모두 지어져야 해당 건물을 지을 수 있다는 설정을 보면 알 수 있듯이 위상 정렬을 쓰는 문제다. 다만 건물 건설 시간이 각각 다르다보니 기교를 가해야한다.

 결론적으론 '위상정렬 + DP' 문제다.

 

Solution

1. topologicalSort 함수

	static int topologicalSort(int N, int W, int[] complete_time, ArrayList<ArrayList<Integer>> graph, int inEdge[])
	{
		//완료시간이 늦는 건물이 가장 마지막에 나오도록
		PriorityQueue<Integer> queue = new PriorityQueue<>((o1, o2) -> complete_time[o1] - complete_time[o2]);

		for(int i = 1;i <= N;i++)
		{
			if(inEdge[i] == 0)
				queue.offer(i);
		}

		while (!queue.isEmpty())
		{
			int now = queue.poll();

			if(now == W)
				break;

			for(int i = 0;i < graph.get(now).size();i++)
			{
				int next = graph.get(now).get(i);

				inEdge[next]--;

				if(inEdge[next] == 0)
				{
					//next를 짓는데 필요한 건물 중 가장 늦게 건설된 건물의 건설 완료시간을 더한다.
					complete_time[next] += complete_time[now];
					queue.offer(next);
				}
			}
		}
		return complete_time[W];
	}

1. complete_time은 초기에 각 건물들의 건설 시간이 들어있다. 이후에 건설완료 시간이 동적으로 기록된다.
2. 우선순위 큐에 건설 완료 시간이 빠른 건물부터 dequeue되도록 정렬한다.
3. 진입 간선이 하나도 없는 건물들부터 queue에 넣는다.
   1. dequeue한 건물 다음으로 지어질 건물들의 inEdge를 하나씩 깎는다.
   2. inEdge[next]가 0이되면 먼저 지어야할 건물들이 모두 지어졌다는 뜻이므로 complete_time[next]에 현재 건물의 건설 완료 시간인 complete_time[now]를 더한다.
   3. 그리고 queue에 넣는다.
   4. 순회 중 W를 만나면 W의 건설 완료시간을 반환하고 종료한다.

 

전체 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;


public class Main {

	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

	public static void solution() throws Exception
	{
		int T = Integer.parseInt(br.readLine());

		for(int t = 0;t < T;t++)
		{
			StringTokenizer strtok = new StringTokenizer(br.readLine());
			int N = Integer.parseInt(strtok.nextToken());//정점 수
			int K = Integer.parseInt(strtok.nextToken());//간선 수
			int constrcut_time[] = new int[N+1];
			int inEdge[] = new int[N+1];

			ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
			strtok = new StringTokenizer(br.readLine());

			for(int i = 0;i <= N;i++)
			{
				graph.add(new ArrayList<>());
				if(i > 0)
					constrcut_time[i] = Integer.parseInt(strtok.nextToken());
			}

			for(int i = 0;i < K;i++)
			{
				strtok = new StringTokenizer(br.readLine());
				int from = Integer.parseInt(strtok.nextToken());
				int to = Integer.parseInt(strtok.nextToken());

				graph.get(from).add(to);
				inEdge[to] ++;
			}
			int W = Integer.parseInt(br.readLine());
			bw.write(topologicalSort(N, W, constrcut_time, graph, inEdge)+"\n");
		}


	}

	static int topologicalSort(int N, int W, int[] complete_time, ArrayList<ArrayList<Integer>> graph, int inEdge[])
	{
		//완료시간이 늦는 건물이 가장 마지막에 나오도록
		PriorityQueue<Integer> queue = new PriorityQueue<>((o1, o2) -> complete_time[o1] - complete_time[o2]);

		for(int i = 1;i <= N;i++)
		{
			if(inEdge[i] == 0)
				queue.offer(i);
		}

		while (!queue.isEmpty())
		{
			int now = queue.poll();

			if(now == W)
				break;

			for(int i = 0;i < graph.get(now).size();i++)
			{
				int next = graph.get(now).get(i);

				inEdge[next]--;

				if(inEdge[next] == 0)
				{
					//next를 짓는데 필요한 건물 중 가장 늦게 건설된 건물의 건설 완료시간을 더한다.
					complete_time[next] += complete_time[now];
					queue.offer(next);
				}
			}
		}
		return complete_time[W];
	}


	public static void main(String[] args) {
		try
		{
			solution();
			bw.close();
			br.close();
		}
		catch (Exception e)
		{
			e.printStackTrace();
		}
	}

}