백준 2637번: 장난감 조립 (Java)

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

2637번: 장난감 조립

문제

우리는 어떤 장난감을 여러 가지 부품으로 조립하여 만들려고 한다. 이 장난감을 만드는데는 기본 부품과 그 기본 부품으로 조립하여 만든 중간 부품이 사용된다. 기본 부품은 다른 부품을 사용하여 조립될 수 없는 부품이다. 중간 부품은 또 다른 중간 부품이나 기본 부품을 이용하여 만들어지는 부품이다.

예를 들어보자. 기본 부품으로서 1, 2, 3, 4가 있다. 중간 부품 5는 2개의 기본 부품 1과 2개의 기본 부품 2로 만들어진다. 그리고 중간 부품 6은 2개의 중간 부품 5, 3개의 기본 부품 3과 4개의 기본 부품 4로 만들어진다. 마지막으로 장난감 완제품 7은 2개의 중간 부품 5, 3개의 중간 부품 6과 5개의 기본 부품 4로 만들어진다. 이런 경우에 장난감 완제품 7을 만드는데 필요한 기본 부품의 개수는 1번 16개, 2번 16개, 3번 9개, 4번 17개이다.

이와 같이 어떤 장난감 완제품과 그에 필요한 부품들 사이의 관계가 주어져 있을 때 하나의 장난감 완제품을 조립하기 위하여 필요한 기본 부품의 종류별 개수를 계산하는 프로그램을 작성하시오.

입력

첫째 줄에는 자연수 N(3 ≤ N ≤ 100)이 주어지는데, 1부터 N-1까지는 기본 부품이나 중간 부품의 번호를 나타내고, N은 완제품의 번호를 나타낸다. 그리고 그 다음 줄에는 자연수 M(3 ≤ M ≤ 100)이 주어지고, 그 다음 M개의 줄에는 어떤 부품을 완성하는데 필요한 부품들 간의 관계가 3개의 자연수 X, Y, K로 주어진다. 이 뜻은 "중간 부품이나 완제품 X를 만드는데 중간 부품 혹은 기본 부품 Y가 K개 필요하다"는 뜻이다. 두 중간 부품이 서로를 필요로 하는 경우가 없다.

출력

하나의 완제품을 조립하는데 필요한 기본 부품의 수를 한 줄에 하나씩 출력하되(중간 부품은 출력하지 않음), 반드시 기본 부품의 번호가 작은 것부터 큰 순서가 되도록 한다. 각 줄에는 기본 부품의 번호와 소요 개수를 출력한다.

정답은 2,147,483,647 이하이다.

 

---

 

풀이

cf) 안 되는 풀이: Queue 만을 사용

N <= 100이니 위상 정렬에서의 indegree 체크 안하고 그냥 방문할때마다 큐에 넣어도 되지 않을까 했는데, 메모리 초과 뜬다

 

풀이 1. 위상 정렬 활용

필요한 개수를 적당히 저장하여(Queue에 같이 들고 가는 방법도 있고, 내 코드처럼 밖에 빼둬도 된다.) 완제품에서부터 위상정렬을 적용하여 푼다.

 

풀이 2. 브루트포스?

N<=100이라 O(N^3) 풀이가 가능하다. 

N부터 1까지 for문을 돌면서, 해당 부품을 하위 부품으로 나눈다. 이 과정을 한 번만 하는 경우 모든 부품이 기본 부품으로 나누어진다는 보장이 없으나, 해당 과정을 N번하면 결국 모든 부품은 기본 부품으로 쪼개진다.

 

 

코드

풀이 1

import java.io.*;
import java.util.*;
 
public class Main {
    public static void main(String[] args) throws IOException {
        StringBuilder sb = new StringBuilder();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[] nums = new int[N+1];
        nums[N] = 1;
        int[] indegree = new int[N+1];
        int M = Integer.parseInt(br.readLine());
        
        List<List<int[]>> graph = new ArrayList<>();
        for (int i = 0; i <= N; i++) {
            graph.add(new ArrayList<int[]>());
        }
        
        for (int i = 0; i < M; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int X = Integer.parseInt(st.nextToken());
            int Y = Integer.parseInt(st.nextToken());
            int K = Integer.parseInt(st.nextToken());
            graph.get(X).add(new int[] {Y, K});
            indegree[Y]++;
        }
        
        Queue<Integer> queue = new ArrayDeque<>();
        queue.offer(N);
        
        while (!queue.isEmpty()) {
            int cur = queue.poll();
            for (int[] temp: graph.get(cur)) {
                int prev = temp[0], need = temp[1];
                nums[prev] += (nums[cur] * need);
                indegree[prev]--;
                if (indegree[prev] == 0) {
                    queue.offer(prev);
                }
            }
            if (graph.get(cur).size() > 0) nums[cur] = 0;
        }
        
        for (int i = 1; i <= N; i++) {
            if (nums[i] > 0) {
                sb.append(i+" "+nums[i]+"\n");
            }
        }
        System.out.println(sb.toString());
    }
}
 

 

풀이 2

import java.io.*;
import java.util.*;
 
public class Main {
    public static void main(String[] args) throws IOException {
        StringBuilder sb = new StringBuilder();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[] nums = new int[N+1];
        nums[N] = 1;
        int M = Integer.parseInt(br.readLine());
        
        List<List<int[]>> graph = new ArrayList<>();
        for (int i = 0; i <= N; i++) {
            graph.add(new ArrayList<int[]>());
        }
        
        for (int i = 0; i < M; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int X = Integer.parseInt(st.nextToken());
            int Y = Integer.parseInt(st.nextToken());
            int K = Integer.parseInt(st.nextToken());
            graph.get(X).add(new int[] {Y, K});
        }
        
        for (int i = 0; i < N; i++) {
            for (int cur = N; cur > 0; cur--) {
                if (nums[cur] == 0) continue;
                for (int[] temp: graph.get(cur)) {
                    int prev = temp[0], need = temp[1];
                    nums[prev] += nums[cur] * need;
                }
                if (graph.get(cur).size() > 0) nums[cur] = 0;
            }
        }
        
        for (int i = 1; i <= N; i++) {
            if (nums[i] > 0) {
                sb.append(i+" "+nums[i]+"\n");
            }
        }
        System.out.println(sb.toString());
    }
}