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

장난감 조립

문제

---

문제 설명

N 이 주어지고 완제품이나 중간부품들을 만드는데 부품들이 얼마나 필요한지 주어진다.

이때, 하나의 완제품을 만드는데 기본 부품들이 얼마나 필요한지 출력하는 문제이다.

---

구현

문제에서 X를 만드는데 Y 라는 부품이 K개 사용된다는 정보가 있다.

이 것을 토대로 위상정렬을 통해서 누적으로 부품의 개수를 세주면 된다.

X는 Y의 상위 부품이니 list[X]에 Y를 K개 추가해준다.

그리고 진입차수를 저장할 indegree 배열은 기초 부품 판단용과 위상 정렬용 두개를 사용한다.

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());
	list[x].add(new Node(y, k));
	
    indegree_x[x]++;
	indegree_y[y]++;
}

그 후에 큐에 최종 부품 번호를 넣고 역방향으로 추적한다.

필요한 부품수는 topologicalSort 함수 내에서 선언한 count 배열로 관리한다.

최종 제품 N 이 1개 필요하므로 count[n] = 1 로 시작한다.

Queue에서 꺼낸 cur.num의 부품을 만들기 위해서 필요한 next.num 이 next.count개 필요하다면
cur.num이 count[cur.num] 개 필요하다.

이렇게 되면 next.num 은 count[cur.num] * next.count 개 필요하게 된다.

while (!queue.isEmpty()) {
	Node cur = queue.poll();

	for (Node next : list[cur.num]) {
		count[next.num] += count[cur.num] * next.count;
		indegree_y[next.num]--;
		if(indegree_y[next.num] == 0)
			queue.add(new Node(next.num, count[next.num]));
	}
}

---

코드

package Gold.G2;

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

public class Main_2637_topologicalSort {
    static class Node{
        int num, count;

        public Node(int num, int count) {
            this.num = num;
            this.count = count;
        }
    }
    static int n, m;
    static int[] indegree_x, indegree_y;
    static ArrayList<Node>[] list;
    static Queue<Node> queue;
    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());
        list = new ArrayList[n + 1];
        for (int i = 1; i <= n; i++) {
            list[i] = new ArrayList<>();
        }

        indegree_x = new int[n + 1];
        indegree_y = new int[n + 1];

        StringTokenizer st;
        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());
            list[x].add(new Node(y, k));
            indegree_x[x]++;
            indegree_y[y]++;
        }

        int[] result = topologicalSort(n);

        for (int i = 1; i <= n; i++) {
            if(indegree_x[i] == 0)
                System.out.println(i + " " + result[i]);
        }
    }

    public static int[] topologicalSort(int n) {
        queue = new LinkedList<>();
        queue.offer(new Node(n, 1));
        int[] count = new int[n + 1];
        count[n] = 1;

        while (!queue.isEmpty()) {
            Node cur = queue.poll();

            for (Node next : list[cur.num]) {
                count[next.num] += count[cur.num] * next.count;
                indegree_y[next.num]--;
                if(indegree_y[next.num] == 0)
                    queue.add(new Node(next.num, count[next.num]));
            }
        }
        return count;
    }
}