[백준] 2637: 장난감 조립 - JAVA

07 Nov 2023 in Algorithm on 다이나믹 프로그래밍

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

풀이

X, Y, K가 주어지는데 X를 만드는데 부품 Y가 K개 필요하다는 뜻이다.

다른 부품으로 만들어지지 않는 기본 부품이 몇개씩 필요한지 구하는 문제이다.

완제품의 번호는 N으로 주어져있다. 따라서, N부터 탐색하면 된다.

위상정렬을 이용했는데 X를 만드는데 Y가 필요하다면 Y의 위상정렬 배열에 +1해줬다.

N부터 시작하여 연결된 부품의 위상을 빼가면서 0이 되면 큐에 추가하는 식으로 구현했다.

---

메모리: 15960KB

시간: 148ms

언어: Java 11

코드

import java.util.*;
import java.io.*;

public class Main {
    static class Node {
        int from;
        int cnt;

        public Node(int from, int cnt) {
            this.from = from;
            this.cnt = cnt;
        }
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int M = Integer.parseInt(br.readLine());

        ArrayList<ArrayList<Node>> list = new ArrayList<>();
        for (int i = 1; i <= N + 1; i++) {
            list.add(new ArrayList<>());
        }

        int[] in_degree = new int[N + 1];
        StringTokenizer st;
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int X = Integer.parseInt(st.nextToken());
            int Y = Integer.parseInt(st.nextToken());
            int K = Integer.parseInt(st.nextToken());
            list.get(X).add(new Node(Y, K));
            in_degree[Y]++;
        }

        Queue<Integer> queue = new LinkedList<>();
        int[] need = new int[N + 1];

        queue.add(N);
        need[N] = 1;

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

            for (Node next : list.get(num)) {
                int from = next.from;
                int cnt = next.cnt;

                need[from] += need[num] * cnt;
                in_degree[from]--;

                if (in_degree[from] == 0) {
                    queue.add(from);
                }
            }
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 1; i < N + 1; i++) {
            if (list.get(i).size() == 0) {
                sb.append(i + " " + need[i]).append("\n");
            }
        }

        System.out.println(sb);
    }

}