[백준] 2637 장난감 조립 - 위상정렬

문제 링크 : https://www.acmicpc.net/problem/2637

🍊해결방법

• 하나의 부품을 만들기 위해서 이전의 부품이 필요함
• 위상정렬 활용
• 기본부품은 1 2 3 4가 아니라 이전 부품이 없는 부품들이다!!!! - 이거 때문에 애 먹었다 ㅎㅎㅎㅎ

😀풀이

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

public class Main {

    static class Node{

        int x, cnt;

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


    }


    static int N;
    static int M;
    static int[] in;
    static int[] in2;
    static int[] count;
    static List<Node>[] list;
    static Queue<Node> q;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // 기본부품, 기타부품
        // 주어진 조건에 따라 정보를 저장
        // N부터 사전에 필요한 부품 개수들을 더하면서 기본 부품의 총 개수 구하기

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

        in = new int[N+1];

        count = new int[N+1];

        list = new List[N+1];

        for(int i = 1; i<=N; i++){
            list[i] = new ArrayList<>();
        }

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

        for(int i=0; i<M; i++){

            StringTokenizer st = new StringTokenizer(br.readLine());

            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int res = Integer.parseInt(st.nextToken());

            list[a].add(new Node(b, res));
            in[b] ++;
        }

        produce();

        // 기본품은 관계가 없는 부품임

        for(int i=1; i<=N; i++){

            if (!list[i].isEmpty()) continue;

            System.out.println(i+" "+count[i]);
        }

    }


    static void produce(){

        q = new LinkedList<>();

        q.add(new Node(N, 1));

        while(!q.isEmpty()){

            Node pn = q.poll();

            int nx = pn.x;
            int pCnt = pn.cnt;


            // 선 조립품들 만들자
            for(int i=0; i<list[nx].size(); i++){

                int next = list[nx].get(i).x;
                int nCnt = list[nx].get(i).cnt;


                count[next] += (pCnt * nCnt);

                in[next]--;

                if (in[next] == 0)
                    q.add(new Node(next, count[next]));

            }

        }

    }


}