[백준] 1005 ACM Craft - 위상정렬(Topology Sort) JAVA

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

1005번: ACM Craft

코드설명

위상정렬 문제입니다.

 

위상정렬이란, 순서가 정해져있는 일련의 작업을 차례대로 수행해야할 떄 사용할 수 있는 알고리즘입니다.

이 문제같은경우, 1번 건물을 지은뒤 4번 건물을 짓기 위해서는 무조건 1번 -> 2번, 1번 -> 3번, 그 이후에 4번을 지을 수 있습니다. 

 

이러한 위상정렬의 예시로는 '선수과목을 고려한 학습순서 설정'과 같은 예시가 있습니다.

각 과목들을 Node로 표현하고, 그 순서를 표현할 수 있습니다.

 

만약 이번 문제에서 간단하게 위상정렬을 활용하여 1번에서 4번 까지 가는 과정을 나타내라. 할경우

1->2->3->4

1->3->2->4 

이렇게 2가지의 답이 나올 수 있습니다.

 

이번 문제같은경우, 4번 건물을 가장 빠르게 지으면서 동시에 2번 3번 건물을 모두 지은채로 4번을 지어야하니, 2번과 3번을 짓는 최대값을 구한뒤 4번을 지으면 됩니다.

 

이떄 헷갈릴 수 있는점은, 아래의 코드에서 왜 inDegree[next] == 0 일때만 answerCost를 갱신해줘야하는것 아닌가라는 의문이 생깁니다.

for(int i=0;i<graph.get(temp).size();i++) {
    int next = graph.get(temp).get(i);
    inDegree[next] -= 1;
    answerCost[next] = Math.max(answerCost[next], answerCost[temp] + D[next]);
    if(inDegree[next] == 0) {
        q.offer(next);
    }
}

위의 코드처럼 매번 건물을 지을떄마다 answerCost[next]를 새로운 값으로 갱신하는 코드인 이유는, 건물이 "동시에" 지어지기 때문입니다. 그렇기에 항상 최대값으로 갱신해야하기에 그렇습니다.

 

 

또한, 이러한 위상정렬 알고리즘을 적용하기 위해서는 신장트리 (Spanning Tree)의 조건에서만 가능합니다.

신장트리란 그래프에서 모든 노드를 포함하면서 사이클이 존재하지 않는 그래프를 의미합니다. ( 모든 노드가 포함되어야하지만, 사이클이 존재해서는 안됩니다.)

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
import java.util.stream.Collectors;

public class Main {
	public static int T, N, K, W;
	public static int[][] map;
	
	public static int[] time;
	public static int[] answerCost;
	public static int[] indegree;
	public static ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();
	public static int answer = 0;
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	T = Integer.parseInt(st.nextToken());
    	
    	for(int t=0;t<T;t++) {
        	st = new StringTokenizer(br.readLine());
        	N = Integer.parseInt(st.nextToken());
        	K = Integer.parseInt(st.nextToken());
        	
        	//인덱스값이 1부터 시작하므로 편리를 위해 N+1 로 설정했습니다.
        	time = new int[N+1]; //각 건물을 짓는데 걸리는 시간
        	indegree = new int[N+1]; //진입차수를 저장합니다.
        	answerCost = new int[N+1]; //각 지점으로 올떄까지의 최대값입니다.
        	graph = new ArrayList<ArrayList<Integer>>();
        	
        	for(int i=0;i<=N;i++)  graph.add(new ArrayList<Integer>()); //그래프 초기화
        	
        	st = new StringTokenizer(br.readLine());
        	for(int i=1;i<=N;i++) {
        		time[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());
        		graph.get(X).add(Y); //X -> Y 로 방향그래프
        		indegree[Y] += 1; // Y로 들어오는 진입차수를 1 증가시킵니다.
        	}
        	
        	st = new StringTokenizer(br.readLine());
        	W = Integer.parseInt(st.nextToken());
        	topologySort();
        	System.out.println(answerCost[W]);
    	}
    	
    }
    
    public static void topologySort() { 
    	Queue<Integer> q = new LinkedList<>();
    	
    	//처음 시작할때는 진입차수가 0인 노드를 큐에 삽입
    	for(int i = 1; i<= N;i++) {
    		if(indegree[i] == 0) {
    			answerCost[i] = time[i];
    			q.offer(i);
    		}
    	}
    	
    	while(!q.isEmpty()) {
    		int now = q.poll();
    		for(int i=0;i<graph.get(now).size();i++) {
    			int next = graph.get(now).get(i);
    			answerCost[next] = Math.max(answerCost[next], answerCost[now] + time[next]); //answerCost[next] = next지점까지의 총 최대 소요시간을 의미합니다. = Math.max(기존의 next지점까지의 총 소요시간, 새롭게 계산한 now지점 + 다음 지점까지의 총 소요시간)의 값을 구합니다.
    			indegree[next] -= 1;     		//해당 원소와 연결된 노드들의 진입차수에서 1 빼기 ( 다른 노드로 들어가는 노드를 처리했습니다. )
    			if(indegree[next] == 0) {
    				q.offer(next);
    			}
    		}
    		
    	}
    }
    
}