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

 문제

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

2637번: 장난감 조립

2637 장난감 조립

 

 구현 방법

완제품을 조립하는데 필요한 기본 부품의 수를 구해야 합니다.

완제품을 조립하기 위해서는 중간 부품과 기본 부품들이 필요한데 중간 부품은 또 다른 중간 부품과 기본 부품으로 구성될 수 있습니다.

기본 부품부터 시작하여 기본 부품을 사용하는 중간 부품 -> 중간 부품과 기본 부품을 사용하는 중간 부품 -> 중간 부품과 기본 부품을 사용하는 완제품의 순서를 지켜야 하고 중간 부품을 사용하는 또 다른 중간 부품이 있을 때 해당 중간 부품이 반복되어 사용되기 때문에 위상정렬과 DP를 사용했습니다.

 

다시 말해, 중간 부품의 구성을 모두 기본 부품으로 변경하여 완제품을 완성했습니다.

글로는 충분히 이해가 가지 않을 것 같아 예제로 예시를 들어보겠습니다.

중간 부품을 5를 구성하는 건 2개의 기본 부품 1과 2개의 기본 부품 2 로 구성됩니다. 

중간 부품을 6을 구성하는 건 2개의 중간 부품 5와 3개의 기본 부품 3, 4개의 기본 부품 4로 구성됩니다.

여기서 중간 부품 5는 5를 구성하는 기본 부품인 1과 2로 바꾸어 저장해줍니다.

마지막으로 완제품 7을 구성하는 건 2개의 중간 부품 5, 3개의 중간 부품 6, 5개의 중간 부품 4 입니다.

이 또한 중간 부품 5를 구성하는 기본 부품 * 개수, 중간 부품 6을 구성하는 기본 부품 * 개수로 저장해 모두 기본 부품으로 만들어 주면 끝!

 

중간 부품을 기본 부품으로 변경할 때는 부품 간의 관계를 저장할 때 관계를 저장하는 리스트와 개수를 저장하는 2차원 배열을 생성하여 사용해주었습니다.

 

 구현 코드

package BOJ.Gold;

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

public class B2637_장난감조립 {
	static int N, M, X, Y, K, inDegree[], arr[][] = new int[101][101]; // arr : 부품 개수 저장
	static boolean base[]; // 기본 부품 확인
	static List<List<Integer>> list = new ArrayList<>(); // 간선 저장
	static List<List<Integer>> partList = new ArrayList<>(); // 완제품 X를 만드는데 필요한 부품 저장
	static Queue<Integer> queue = new LinkedList<>(); // 위상 정렬을 돌리기 위한 큐
	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());
		StringBuilder sb = new StringBuilder();
		StringTokenizer st = null;
		inDegree = new int[N+1];
		base = new boolean[N+1];
		for (int i=0;i<=N;i++) {
			list.add(new ArrayList<>());
			partList.add(new ArrayList<>());
		}
		for (int i=0;i<M;i++) {
			st = new StringTokenizer(br.readLine());
			X = Integer.parseInt(st.nextToken());
			Y = Integer.parseInt(st.nextToken());
			K = Integer.parseInt(st.nextToken());
			inDegree[X]++;
			list.get(Y).add(X);
			partList.get(X).add(Y); // 완제품 또는 중간부품 X를 만드는데 필요한 부품은 Y
			arr[X][Y] += K; // 완제품 또는 중간부품 X를 만드는데 필요한 부품의 개수는 K
		}
		topology();

		for (int i=1;i<=N;i++) {
			if (base[i]) sb.append(i+" "+arr[N][i]+"\n"); // 완제품 N의 기본 부품 출력
		}
		
		System.out.println(sb);
	}
	
	static void topology() {
		for (int i=1;i<=N;i++) {
			if (inDegree[i] == 0) { // 진입 차수가 0 == 기본 부품
				base[i] = true; // 기본 부품 처리
				queue.offer(i);
			}
		}
		
		while(!queue.isEmpty()) {
			int now = queue.poll();
			if (now == N) return;
			for (int next : list.get(now)) {
				if (--inDegree[next] == 0) {
					queue.offer(next);
					
					List<Integer> needParts = partList.get(next); // 다음 부품을 만들기 위해 필요한 부품들
					int size1 = needParts.size();
					for (int i=0;i<size1;i++) {
						Integer needPart = needParts.get(i);
						if (base[needPart]) continue; // 기본 부품이라면 continue
						List<Integer> baseParts = partList.get(needPart); // 필요한 부품들이 가진 기본 부품들
						int size2 = baseParts.size();
						for (int j=0;j<size2;j++) {
							Integer basePart = baseParts.get(j);
							// 필요한 부품들이 가진 기본 부품 * 부품의 개수
							arr[next][basePart] += arr[needPart][basePart] * arr[next][needPart]; 
							// 존재하는 기본 부품이 아니라면 추가
							if (!needParts.contains(basePart)) needParts.add(basePart); 
						}
						// 필요한 부품들이 가진 기본 부품을 추가해줬기 때문에 중간 부품은 삭제
						needParts.remove(i); 
						i--; size1--; // 하나를 삭제했으니 인덱스와 사이즈도 삭제
					}
				}
			}
		}
	}
}

 

정답!