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

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

 

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

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

---

1.  아이디어

 

번호와 개수를 갖는 노드를 활용한 위상 정렬과 다이나믹 프로그래밍으로 해결할 수 있었다.

---

2. 문제풀이

 

장난감의 개수를 간선의 가중치로 생각하는 방향 비순환 그래프에서 위상 정렬로 구현했다. 위상 정렬 과정에서는 카운팅 배열에 장난감 부품의 개수를 저장했는데 노드를 정렬할 때마다 후행 작업에 선행 작업의 개수를 전달하면 부품 수를 전달할 수 있다. 이후 진출차수 배열에서 0인 노드가 기본 부품임을 이용해서 출력하는 방식으로 구현했다.

---

3. 코드

 

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

public class Main {

    private static class Node {
        int v;
        int cnt;

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

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;

        int N = Integer.parseInt(br.readLine());
        int M = Integer.parseInt(br.readLine());

        List<List<Node>> adj = new ArrayList<>();
        for (int i = 0; i <= N; i++) {
            adj.add(new ArrayList<>());
        }

        int[] indegree = new int[1 + N];
        int[] outdegree = new int[1 + N];

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

            adj.get(X).add(new Node(Y, K));
            indegree[Y]++;
            outdegree[X]++;
        }

        int[] cntArr = topologicalSort(N, adj, indegree);
        for (int i = 1; i <= N; i++) {

            // 진출차수가 0인 부품이 기본 부품
            if (outdegree[i] == 0) {
                sb.append(i).append(" ").append(cntArr[i]).append("\n");
            }
        }

        bw.write(sb.toString());
        bw.flush();
    }

    private static int[] topologicalSort(int N, List<List<Node>> adj, int[] indegree) {
        int[] cntArr = new int[1 + N];
        cntArr[N] = 1;

        Queue<Node> q = new ArrayDeque<>();
        q.add(new Node(N, 1));

        while (!q.isEmpty()) {
            Node node = q.remove();

            for (Node next : adj.get(node.v)) {
                indegree[next.v]--;
                if (indegree[next.v] == 0) q.add(new Node(next.v, cntArr[next.v]));

                cntArr[next.v] += cntArr[node.v] * next.cnt;
            }
        }

        return cntArr;
    }

}

---

4. 후기