백준 2637번 : 장난감 조립 java

이 문제는 위상 정렬을 이용하여 부품을 만들어야 하는 우선순위를 만든 뒤 우선순위에 있는 부품을 만들기 위해서 필요한 우선순위가 뒤에 있는 부품의 개수를 더하며 푸는 문제입니다.

위의 예제 입력 1번을 예시로 설명하겠습니다.

예제 입력 1번의 N은 7입니다.

N은 만들어야하는 개수가 1개입니다.

7을 만들기 위해서는 우선 6을 3개, 5를 2개, 4를 5개 만들어야 합니다.

그리고 6을 1개 만들기 위해서는 3을 3개, 4를 4개, 5를 2개 만들어야 합니다.

이때 6을 3개 만들어야 하므로 3을 3x3인 9개, 4를 12개, 5를 6개 만들어야 합니다.

그리고 5를 만들기 위해서는 1을 2개, 2를 2개 만들어야 합니다.

5는 7을 만들기 위해서 2개, 6을 만들기 위해서 6개가 필요해 총 8개가 필요합니다.

따라서 이를 만들기 위해 1이 16개, 2가 16개 필요합니다.

따라서 총부품의 수는 1이 16개, 2가 16개, 3이 9개, 4가 17개 필요합니다.

이 과정을 코드로 표현해보겠습니다.

---

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

public class Main {
    static int N;
    static int[] needNum;
    static int[] parentNum;
    static List<List<Node>> l = new ArrayList<>();

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());
        int M = Integer.parseInt(br.readLine());

        needNum = new int[N+1];
        parentNum = new int[N+1];
        for(int i = 0; i<=N; i++)
            l.add(new ArrayList<>());

        while(M-->0){
            StringTokenizer st = new StringTokenizer(br.readLine());

            int A = Integer.parseInt(st.nextToken());
            int B = Integer.parseInt(st.nextToken());
            int need = Integer.parseInt(st.nextToken());

            l.get(A).add(new Node(B, need));
            parentNum[B]++;
        }

        topologicalSort();

        for(int i = 1; i<N; i++)
            if(l.get(i).size() == 0)
                System.out.println(i+" "+needNum[i]);
    }

    static void topologicalSort(){
        Queue<Integer> q = new LinkedList<>();
        q.offer(N);
        needNum[N] = 1;

        while(!q.isEmpty()){
            int vertex = q.poll();

            for(int i = 0; i<l.get(vertex).size(); i++){
                Node nextV = l.get(vertex).get(i);

                needNum[nextV.vertex] += needNum[vertex] * nextV.need;
                parentNum[nextV.vertex]--;

                if(parentNum[nextV.vertex] == 0)
                    q.offer(nextV.vertex);
            }
        }
    }
}
class Node{
    int need, vertex;

    Node(int vertex, int need){
        this.vertex = vertex;
        this.need = need;
    }
}

이 문제를 풀 때 조심하셔야 하는 점은 기본 부품은 1, 2, 3, 4로 정해져 있는 것이 아니라 다른 부품들로 만들 수 없는 부품들을 의미한다는 것입니다.