[알고리즘] 위상 정렬

위상 정렬이란?

깔끔하게 정리해주신 블로그를 첨부(보고 이해가 안 될 수가 없을듯..)
https://bcp0109.tistory.com/21

실전 문제 풀이(백준 1005)

import java.util.*;
 
public class Main {    
 
    static int n, w;
    static ArrayList<Integer>[] list; //연결 간선 정보
    static int[] building; //빌딩 짓는 비용 정보
    static int[] indegree;
    static int[] buildCost; //각 위치까지 빌딩을 짓는 비용의 최대값을 저장한다.
    
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
 
        int t = scan.nextInt();
        for(int i = 0; i < t; i++) {
            n = scan.nextInt();
            int k = scan.nextInt();
            
            building = new int[n + 1];
            list = new ArrayList[n + 1];
            for(int j = 1; j <= n; j++) {
                building[j] = scan.nextInt();
                list[j] = new ArrayList<>();
            }
            
            indegree = new int[n + 1];
            for(int j = 0; j < k; j++) {
                int s = scan.nextInt();
                int e = scan.nextInt();
                list[s].add(e); 
                indegree[e]++;
            }
            w = scan.nextInt(); //건설해야 할 건물의 번호
            
            buildCost = new int[n + 1]; 
            topologySort();
            System.out.println(buildCost[w]);
        }
    }
    
    public static void topologySort() {
        Queue<Integer> q = new LinkedList<>();
        for(int i = 1; i < indegree.length; i++) {
            if(indegree[i] == 0) {
                buildCost[i] = building[i];
                q.offer(i);
            }
        }
        
        while(!q.isEmpty()) {
            int current = q.poll();
            
            for(int i = 0; i < list[current].size(); i++) {
                int next = list[current].get(i);
                buildCost[next] = Math.max(buildCost[current] + building[next], buildCost[next]);
                indegree[next]--;
                if(indegree[next] == 0) q.offer(next);
            }
        }
    }
}

얻어갈 점:

• dfs와 다르게 위상 정렬은 양 방향 연결이 아니기에 list[s].add(e) 까지만!
  
• 핵심 로직은 이 부분인데 원래 최대 값을 담는 것은 int sum=0; 이런 식의 변수를 이용하여 구현해왔으나, static int[] buildCost와 같이 구현하여 각 배열의 인덱스들이 정렬되면서 누적합의 형태로 Math.max를 사용하여 최대값 저장