[백준] 2637 장난감 조립 - Java

 

 

문제 출저

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

2637번: 장난감 조립

 

 

문제 풀이

장난감의 종류와 각 장난감이 조립되기 위한 부품들을 알려줍니다. 이 때, 부품은 기본 부품과 중간 부품이 있습니다. 기본 부품은 다른 부품 조립에 사용되는 부품으로 다른 부품으로 조립할 수 없는 기본 부품 입니다. 중간 부품은 부품들로 이루어진 부품들입니다. 최종 완제품 N을 조립하는게 기본 부품이 몇 개 필요한지 구하는게 이 문제의 요구사항 입니다. 

 

 

위상 정렬로 풀었습니다. 

클래스 part(int index, int number) 를 생성하여 몇 번째 부품이 몇 개 필요한지 저장했습니다. 

List<part>[] partList 를 선언하여 제품을 만드는데 어떤 부품이 몇 개가 필요한지를 저장했습니다.

int[] need를 선언하여 이 부품이 몇 개의 부품의 가짓수가 필요한지 저장했습니다.

boolean[] basic 을 선언하여 기본 부품을 true로 저장했습니다.

static int[] part 을 선언하여 완제품을 위한 필요한 부품들의 갯수를 저장했습니다. 

 

입력을 받을 때 partList에 저장하고 need의 가짓수를 올립니다.

입력을 다 받고 난 후 partList를 for문으로 순회하면서 사이즈가 0인 부품은 기본 부품이므로 해당 부붐의 basic을 true로 바꿉니다.

Queue<Integer> 를 선언하여 완제품을 N을 넣고 탐색을 진행합니다. 

While을 이용해 que가 빌 때 까지 탐색합니다.

하나를 꺼내 part 부분에 현재 꺼낸 갯수와 필요한 갯수를 곱하여 더합니다.

need에 탐색을 마친 index를 뺍니다. 이 때 need가 0이 되면 다시 que에 넣습니다. (필요한 조건을 충족했으니 탐색 대상이 됨)

이런 식으로 탐색을 반복하여 part를 완성합니다.

basic을 순회하면서 true인 index와 같은 위치인 part를 출력합니다. 

 

 

소스 코드

package baekjoon.backjoon9.day25;

/*
장난감 조립
https://www.acmicpc.net/problem/2637
 */

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class B2637 {

    static int n, m;
    static List<part>[] partList;
    static int[] need; // 필요한 갯수
    static boolean[] basic; // 기본 부품
    static int[] part; // 부품 갯수


    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());

        partList = new List[n + 1];
        for (int i = 0; i < n + 1; i++) {
            partList[i] = new ArrayList<>();
        }

       need = new int[n+1];

       StringTokenizer st = null;

       for(int i = 0; i < m; i++) {
           st = new StringTokenizer(br.readLine());

           int target = Integer.parseInt(st.nextToken());
           int needIndex = Integer.parseInt(st.nextToken());
           int needNumber = Integer.parseInt(st.nextToken());

           partList[target].add(new part(needIndex, needNumber));

           need[needIndex]++;
       }

       basic = new boolean[n+1];

       for(int i = 1; i < n; i++) {
           if(partList[i].size() == 0) {
               basic[i] = true;
           }
       }

       part = new int[n + 1];
       part[n] = 1;

       Queue<Integer> que = new LinkedList<>();
       que.add(n);


        while (!que.isEmpty()) {
            Integer index = que.poll();

            for(part p : partList[index]) {
                part[p.index] += p.number * part[index];
                need[p.index] -= 1;

                if(need[p.index] == 0) {
                    que.add(p.index);
                }
            }
        }

        StringBuilder sb = new StringBuilder();

        for(int i = 1; i < n+1; i++) {
            if(basic[i]) {
                sb.append(i).append(" ").append(part[i]).append("\n");
            }
        }

        System.out.println(sb);


    }

    public static class part {
        int index;
        int number;

        part(int index, int number) {
            this.index = index;
            this.number = number;
        }
    }





}