[위상정렬] 장난감 조립(백준 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 이하이다.)

구현

1. 위상 정렬, dp 알고리즘 이용
2. indegree[n]에 각 n번 부품의 input degree 개수 기록
3. indegree[n]=0이면 큐에 넣기(초반에  indegree[n]=0이면, n은 기본 부품을 의미)
4. arrList배열 사용: arr[a].add(new int: b 부품을 만들기 위해 a개 c개 필요하다(데이터 입력 시 )
5. count[x][y]: x개의 부품을 만들기 위해 필요한 y의 개수

for(int i=0;i<arr[n].size();i++) {
				int t_n=arr[n].get(i)[0]; //타겟 부품
				int amount=arr[n].get(i)[1]; //기본 부품의 개수 
				
				//dp
				for(int j=1;j<N;j++) { 
					count[t_n][j]+=count[n][j]*amount;
				}
				
				indegree[t_n]--; 
				if(indegree[t_n]==0) q.add(t_n);
			}

 

 

총 코드 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

	static int N;
	static int M;
	static ArrayList<int[]>[] arr;
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N=Integer.parseInt(br.readLine());
		M=Integer.parseInt(br.readLine());
	
		int[][] count=new int[N+1][N];
		int[] indegree=new int[N+1];
		arr=new ArrayList[N+1];
		
		for(int i=1;i<=N;i++) {
			arr[i]=new ArrayList<>();
			
		}
		for(int i=1;i<=M;i++) {
			StringTokenizer st=new StringTokenizer(br.readLine());
			int a=Integer.parseInt(st.nextToken());
			int b=Integer.parseInt(st.nextToken());
			int c=Integer.parseInt(st.nextToken());
			
			arr[b].add(new int[] {a,c}); //a를 위해서는 b가 c개 필요하다.  
			indegree[a]++;
		}
		
		Queue<Integer> q=new LinkedList<>();
		
		for(int i=1;i<N;i++) {
			if(indegree[i]==0) {
				q.add(i);
				count[i][i]=1;
			}
			
		}
		
		while(!q.isEmpty()) {
			
			int n=q.poll(); //기본 부품 
			
			for(int i=0;i<arr[n].size();i++) {
				int t_n=arr[n].get(i)[0]; //타겟 부품
				int amount=arr[n].get(i)[1]; //기본 부품의 개수 
				
				for(int j=1;j<N;j++) {
					count[t_n][j]+=count[n][j]*amount;
				}
				
				indegree[t_n]--;
				if(indegree[t_n]==0) q.add(t_n);
			}
		}
			
		for(int i=1;i<N;i++) {
			if(count[N][i]>0)
				System.out.println(i+" "+count[N][i]);
		}
	}

}