[Java] 백준 2637번: 장난감 조립

[문제 바로 가기] - 장난감 조립

📌 유형 : 위상 정렬 + DP + 그래프 탐색

처음에는 자료구조 차원에서 풀이할 수 있는 문제라고 생각하여, List와 Map을 사용해서 각 중간 부품이나 완제품에 필요한 부품들의 개수를 더해주려고 했다.

하지만 이 문제는 각 부품(또는 완제품)에 필요한 부품들을 구하는 순서가 중요하기 때문에 위상 정렬을 꼭 사용해야 함을 알게 되었다.

💡 아이디어

위상 정렬에 대한 내용은 이전에 풀이했던 위상정렬 문제를 바탕으로 이해했다.

7
8
5 1 2
5 2 2
7 5 2
6 5 2
6 3 3
6 4 4
7 6 3
7 4 5

이 문제도 예제에서 5 -> 6 -> 7 순서로 필요한 부품들을 먼저 구하는 것이 좋고, 사이클이 없어야 하므로 유향 그래프 문제가 된다.

1. 후행하는 노드들의 진입 차수 indegree 구하고, 완성품 X를 만들기 위한 Y와 K 넣기

	for (int i = 0; i < M; i++) {
		st = new StringTokenizer(br.readLine());
		int X = Integer.parseInt(st.nextToken()); // 완성품
        int Y = Integer.parseInt(st.nextToken()); // 부품
        int K = Integer.parseInt(st.nextToken()); // 개수

        graph[Y].add(new int[]{X, K}); // Y K개로 X를 만들기
        indegree[X]++; // 진입 차수 계산
	}

2. 진입 차수가 0인 부품들 Queue에 넣기

	for (int i = 1; i <= N; i++) {
		if (indegree[i] == 0) { // 기본 부품일 경우
			q.add(i); // 큐에 넣기
			dp[i][i] = 1; // 기본 부품은 본인 1개만 필요
		}
	}

3. BFS 탐색하면서 DP 배열 갱신하고 진입 차수가 0이 되는 경우 Queue에 넣기

	while (!q.isEmpty()) {
		int cur = q.poll();

		for (int[] next : graph[cur]) {
			int target = next[0]; // 만들 수 있는 부품 또는 완제품
            int need = next[1]; // 필요한 개수

            for (int i = 1; i <= N; i++) {
                dp[target][i] += dp[cur][i] * need;
            }

            indegree[target]--;

             // 차수가 0이 되면 큐에 넣기 : 차수가 적은 것부터 탐색할 수 있도록
            if (indegree[target] == 0) q.add(target);
        }
    }

---

풀이

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

public class Main {
    static int N;
    static List<int[]>[] graph; // 부품 저장 리스트
    static int[] indegree; // 진입 차수 저장할 배열
    static int[][] dp; // dp[X][Y] : X를 만들기 위해 필요한 기본 부품 Y의 개수

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine()); // 완제품 번호
        int M = Integer.parseInt(br.readLine());

        StringTokenizer st;

        graph = new ArrayList[N + 1];
        indegree = new int[N + 1];
        dp = new int[N + 1][N + 1];

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

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int X = Integer.parseInt(st.nextToken()); // 완성품
            int Y = Integer.parseInt(st.nextToken()); // 부품
            int K = Integer.parseInt(st.nextToken()); // 개수

            graph[Y].add(new int[]{X, K}); // Y K개로 X를 만들기
            indegree[X]++; // 진입 차수 계산
        }

        bfs();

        for (int i = 1; i < N; i++) {
            if (dp[N][i] > 0) {
                System.out.println(i + " " + dp[N][i]);
            }
        }
    }

    public static void bfs() {
        Queue<Integer> q = new ArrayDeque<>();

        for (int i = 1; i <= N; i++) {
            if (indegree[i] == 0) { // 기본 부품일 경우
                q.add(i); // 큐에 넣기
                dp[i][i] = 1; // 기본 부품은 본인 1개만 필요
            }
        }

        while (!q.isEmpty()) {
            int cur = q.poll();

            for (int[] next : graph[cur]) {
                int target = next[0]; // 만들 수 있는 부품 또는 완제품
                int need = next[1]; // 필요한 개수

                for (int i = 1; i <= N; i++) {
                    dp[target][i] += dp[cur][i] * need;
                }

                indegree[target]--;

                // 차수가 0이 되면 큐에 넣기 : 차수가 적은 것부터 탐색할 수 있도록
                if (indegree[target] == 0) q.add(target);
            }
        }
    }
}