[백준 2637 JAVA] 장난감 조립

 

위상정렬 문제이다.

문제만 보면 N번째 장난감이 마지막에 해당될 것 같지만 역으로 N번째 장난감부터 탐색을 진행해야된다.

필요한 요소들의 개수를 판단하는 것이기 때문에 N번째 장난감부터 탐색을 해야 atomic한 장난감부품의 필요한 갯수를 알 수 있다.

(atomic한 부품부터 N번째 장난감으로 탐색할 수 있지만 필요한 데이터가 너무 많아진다)

 

inputRoot를 활용하여 더이상 해당 부품의 요구 갯수가 없을 때 까지 탐색을 하고, 해당 부품의 InputRoot가 0일때는 더이상 해당 부품이 추가될 일이 없으므로 해당 부품을 이루는 다른 부품이 몇개 필요한 지 탐색이 가능하게 된다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Queue;
import java.util.StringTokenizer;

class Main {
    static int N, M;
    static ArrayList<Require>[] graph;
    static int[] inputRoot;
    static int[] require;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        M = Integer.parseInt(br.readLine());
        graph = new ArrayList[N + 1];
        inputRoot = new int[N + 1];
        require = new int[N + 1];
        for (int i = 1; i <= N; i++) {
            graph[i] = new ArrayList<>();
        }
        StringTokenizer st;
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int dir = Integer.parseInt(st.nextToken());
            int require = Integer.parseInt(st.nextToken());
            graph[a].add(new Require(dir, require));
            inputRoot[dir]++;
        }
        Queue<Integer> q = new ArrayDeque<>();
        q.offer(N);
        require[N] = 1;
        while (!q.isEmpty()) {
            int cur = q.poll();
            for (int i = 0; i < graph[cur].size(); i++) {
                Require temp = graph[cur].get(i);
                require[temp.dir] += require[cur] * temp.require;
                inputRoot[temp.dir]--;
                if (inputRoot[temp.dir] == 0) {
                    q.offer(temp.dir);
                }
            }
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 1; i < N; i++) {
            if (graph[i].isEmpty()) {
                sb.append(i).append(" ").append(require[i]).append("\n");
            }
        }
        System.out.println(sb);

    }
}

class Require {
    int dir, require;

    public Require(int dir, int require) {
        this.dir = dir;
        this.require = require;
    }
}