[백준]2637: 장난감 조립 - JAVA

[백준]2637: 장난감 조립

2637번: 장난감 조립

풀이

🪑 처음 문제를 읽을 때는 다익스트라나 플로이드 와샬인가 싶다가 부품별로 만들어 지는 순서가 중요하다는 조건을 보고 위상정렬이 떠올랐다!

 

📝 문제의 조건을 보자.

• 완제품 N을 만드는데 필요한 모든 기본 부품의 종류와 수를 구해야 한다.
• 각 정보는 X번 부품을 만드는데 Y부품 K개가 필요함을 의미한다.
• 주어지지 않은 정보는 기본 부품이 된다는 것을 알 수 있다.

 

 

🔧 문제를 풀어보자!

1. 정보를 입력 받을 때 X, Y의 진입 간선 정보를 모두 저장한다.
2. 위상정렬을 하되, N번 노드부터 시작한다.
3. 결과를 출력한다.

 

🔹 정보를 입력 받을 때 X, Y의 진입 간선 정보를 모두 저장한다.

- 위상정렬 알고리즘을 활용하여 연결 노드를 탐색할 때 N번 노드에서 부터 시작 할 것이므로 Y에 대한 진입간선 정보가 필요하다.

- 기본 부품의 정보를 알기 위해 X에 대한 진입 간선의 정보가 필요하다. X로 오는 진입 간선이 없다면 기본 부품이 된다.

 

🔹 위상정렬을 하되, N번 노드부터 시작한다.

- N -> 연결 노드로 탐색한다.

- 탐색할 때에는 다음 탐색할 부품이 몇개 필요한지 저장해 주어야 한다. 이때 현재 부품의 필요 개수에 다음 부품을 만드는데 필요한 개수를 곱한다음 누적하여 더해준다. 

 

🔹 결과를 출력한다.

- 이때 X의 진입 간선의 정보를 사용하여 기본 부품에 해당하는 정보만 출력해 준다.

 

 

코드

import java.io.*;
import java.util.*;
 
public class Main {
 
    static int[] indegree_y;
    static ArrayList<Node>[] list;
 
    public static void main(String[] args) throws IOException {
        
        //입력
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
 
        int n = Integer.parseInt(bf.readLine());
        int m = Integer.parseInt(bf.readLine());
 
        list = new ArrayList[n + 1];
        for(int i = 1; i <= n; i++) {
            list[i] = new ArrayList<>();
        }
 
        int[] indegree_x = new int[n + 1]; //기본 부품 찾기 용도
        indegree_y = new int[n + 1]; //위상정렬 용도
        for(int i = 0; i < m; i++) {
            String str = bf.readLine();
            StringTokenizer st = new StringTokenizer(str);
            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 = topologySort(n);
        for(int i = 1; i <= n; i++) {
            if(indegree_x[i] == 0) System.out.println(i + " " + result[i]);
        }
    }
 
    public static int[] topologySort(int n) {
        Queue<Node> q = new LinkedList<>();
        q.offer(new Node(n, 1));
        int[] counter = new int[n + 1];
        counter[n] = 1;
 
        while(!q.isEmpty()) {
            Node current = q.poll();
 
            for(int i = 0; i < list[current.num].size(); i++) {
                Node next = list[current.num].get(i);
                counter[next.num] += counter[current.num] * next.count;
                indegree_y[next.num]--;
                if(indegree_y[next.num] == 0) q.offer(new Node(next.num, counter[next.num]));
            }
        }
        return counter;
    }
 
    public static class Node {
        int num, count;
 
        public Node(int num, int count) {
            this.num = num;
            this.count = count;
        }
    }
}