[BOJ] 2637. 장난감 조립

위상정렬을 이용한 그래프 문제였다.

이 문제는 부품사이의 순위가 존재하고 서로 이어보면 DAG를 형성할 수 있기에 위상정렬을 사용해보았다. 큰부품 -> 작음부품이렇게 바라보도록 그래프를 그리고, 갯수만큼 곱해주면서 위상정렬을 돌면 최소부품이 몇개 필요한지 찾을 수 있는 간단한 문제였다. 

package algostudy2;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main_bj_2637_장난감조립 {
 
    static int N;
    static int[][] graph;
    static int[] indegree;
 
    static boolean[] isSmallest;
    static int[] cost;
 
    static Queue<Integer> queue;
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
 
        N = Integer.parseInt(br.readLine());
        graph = new int[N + 1][N + 1];
        indegree = new int[N + 1];
        isSmallest = new boolean[N + 1];
        cost = new int[N + 1];
 
        for (int i = 1; i <= N; i++) {
            isSmallest[i] = true;
        }
 
        int W = Integer.parseInt(br.readLine());
 
        for (int i = 0; i < W; i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int weight = Integer.parseInt(st.nextToken());
 
            graph[start][end] = weight;
            isSmallest[start] = false;
            indegree[end] += 1;
        }
 
        queue = new LinkedList<>();
        for (int i = 1; i <= N; i++) {
            if (indegree[i] == 0) {
                cost[i] = 1;
                queue.offer(i);
            }
        }
 
        topological();
 
        StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= N; i++) {
            if (isSmallest[i] == true) {
                sb.append(i + " " + cost[i] + "\n");
            }
        }
 
        System.out.print(sb.toString());
    }
 
    static void topological() {
 
        while (!queue.isEmpty()) {
            int cur = queue.poll();
 
            for (int index = 1; index <= N; index++) {
                if (graph[cur][index] != 0) {
                    int next = index;
 
                    indegree[next] -= 1;
 
                    cost[next] += cost[cur] * graph[cur][next];
 
                    if (indegree[next] == 0) {
                        queue.offer(next);
                    }
                }
            }
        }
    }
}