백준 - 장난감 조립 (2637) : JAVA

문제 유형
위상 정렬

풀이 방법 도출
문제의 조건은 다음과 같습니다.

1. 우리는 어떤 장난감을 여러 가지 부품으로 조립하여 만들려고 한다. 이 장난감을 만드는데는 기본 부품과 그 기본 부품으로 조립하여 만든 중간 부품이 사용된다.
2. 본 부품은 다른 부품을 사용하여 조립될 수 없는 부품이다. 중간 부품은 또 다른 중간 부품이나 기본 부품을 이용하여 만들어지는 부품이다.
3. 이와 같이 어떤 장난감 완제품과 그에 필요한 부품들 사이의 관계가 주어져 있을 때 하나의 장난감 완제품을 조립하기 위하여 필요한 기본 부품의 종류별 개수를 계산하는 프로그램을 작성하시오.
4. 두 중간 부품이 서로를 필요로 하는 경우가 없다.

선후관계가 있는 문제이기 때문에 위상 정렬 알고리즘을 떠올릴 수 있습니다.

또한 이 문제에서 힌트가 될 만한 문장이 하나 존재합니다
"두 중간 부품이 서로를 필요로 하는 경우가 없다."
-> 이 말은 즉 사이클이 존재하지 않는 다는 뜻입니다.

위상 정렬은 사이클이 존재하지 않아야 가능하기 때문에 위상 정렬로 풀어도 되겠다는 확신을 가질 수 있습니다.
하지만 일반적인 위상 정렬 알고리즘과는 약간 다릅니다.

만약 기본 부품부터 방문한다면, 기본 부품이 몇개 필요한지 알 수 없습니다.
-> 완제품부터 방문한다면, 해결할 수 있습니다.

static void bfs() {

    Queue<Integer> q = new ArrayDeque<>();

    answer[n] = 1;

    q.add(n);

    while (!q.isEmpty()) {

        int cur = q.poll();

        for (Node next : map.get(cur)) {
            rank[next.num]--;
            answer[next.num] += answer[cur] * next.need;
            if (rank[next.num] == 0) q.add(next.num);
        }
    }

}

위와 같이 완제품부터 순차적으로 방문해줍니다.

이후에는 일반적인 위상정렬 로직과 같습니다.
결국, 간선의 방향을 어떻게 하느냐가 관건인 문제였습니다.

시간 복잡도
O(N + M)

코드

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

class Node {
    int num;
    int need;

    Node (int num, int need) {
        this.num = num;
        this.need = need;
    }
}

public class Main {

    static List<List<Node>> map;
    static int[] rank;
    static int[] answer;
    static int n;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());

        rank = new int[n+1];
        answer = new int[n+1];
        map = new ArrayList<>();

        for (int i=0; i<=n; i++) {
            map.add(new ArrayList<>());
        }

        st = new StringTokenizer(br.readLine());

        int m = Integer.parseInt(st.nextToken());

        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());

            map.get(x).add(new Node(y,k));

            rank[y]++;
        }

        bfs();

        for (int i=1; i<=n; i++) {
            if (map.get(i).isEmpty()) {
                System.out.println(i + " " + answer[i]);
            }
        }

    }

    static void bfs() {


        Queue<Integer> q = new ArrayDeque<>();

        answer[n] = 1;

        q.add(n);

        while (!q.isEmpty()) {

            int cur = q.poll();

            for (Node next : map.get(cur)) {
                rank[next.num]--;
                answer[next.num] += answer[cur] * next.need;
                if (rank[next.num] == 0) q.add(next.num);
            }
        }

    }

}