백준 2637 (장남감 조립) - java

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

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번째 정점이 필요한 부품의 개수이므로 n번째 지점을 시작으로 위상정렬을 수행하는 것이다.
• 결국 위상정렬을 완료할 경우 기본 부품들의 개수를 알 수 있다.

전체 코드

import java.util.*;
import java.io.*;
public class Main {

    static int n = 0;
    static int m = 0;

    static ArrayList<Node>[] graph;

    static int[] inputArr;

    static int[] count;

    public static void main(String[] args) throws Exception {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine(), " ");
        StringBuilder sb = new StringBuilder();
        n = Integer.parseInt(st.nextToken());

        inputArr = new int[n+1];
        graph = new ArrayList[n+1];
        count = new int[n+1];

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

        st = new StringTokenizer(bf.readLine(), " ");
        m = Integer.parseInt(st.nextToken());

        for(int i=1;i<=m;i++){
            st = new StringTokenizer(bf.readLine(), " ");
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());

            graph[x].add(new Node(y,c)); // 간선 정보를 반대로 기입
            inputArr[y] += 1;
        }

        PriorityQueue<Integer> pq = new PriorityQueue<>(
                (x,y) -> x - y
        );

        Queue<Node> q = new LinkedList<>();
        q.add(new Node(n,1)); // n번째 정점을 시작으로 위상정렬 수행
        count[n] = 1; 

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

            if(graph[cur.v].size() == 0){
                pq.add(cur.v);
            }

            for(Node next : graph[cur.v]){
                inputArr[next.v] -= 1;

                count[next.v] += (next.c * cur.c);

                if(inputArr[next.v] == 0){
                    q.add(new Node(next.v,count[next.v]));
                }
            }
        }

        while(!pq.isEmpty()){
            int cur = pq.poll();
            sb.append(cur+" "+count[cur]+"\n");
        }
        System.out.print(sb);


        bf.close();
    }
}
class Node{
    int v;
    int c;

    Node(int v,int c){
        this.v = v;
        this.c = c;
    }
}