[JAVA] 백준 2637번 【G2.장난감 조립】

문제

2637번: 장난감 조립

 

풀이

1️⃣ 위상정렬을 이용한 풀이

💡 떠오른 Idea

일단 부품의 조립 순서가 있으므로 위상 정렬을 사용해야한다는 것은 파악했다.

근데, 원하는 출력은 최종 장난감을 구성하는 기본 부품의 수를 출력해야했다.

기본 부품은 조합되어 만들어진 부품이 아닌 경우 기본 부품이라고 한다.

따라서, 특정 부품을 조립할때마다 해당 조립 부품을 구성하는 기본 부품의 정보를 저장하고 계속 넘겨주어야겠다고 생각했다.

일단, indegree 값이 0 인 경우 기본 부품이라고 할 수 있고 기본 부품은 자기 자신 1개로 이루어진다.

예제를 예를 들면,


1번 부품은

[기본 부품 1: 1개 ] 로 이루어져있다.



5번 부품은 1번 부품 2개가 필요하므로

1번 부품이 가진 모든 기본 부품의 2배가 필요하다.

따라서, 5번 부품의 경우

[기본 부품 1 : 2개] 가 된다.

그리고 2번 부품 2개도 필요하므로

5번 부품의 경우

[기본 부품 1 : 2개 , 기본 부품 2 : 2개] 가 된다. 

더이상 5번 부품을 구성하는데 필요한 부품이 더 없으므로 마무리 된다.



이제 7번 부품의 경우 5번 부품 2개가 필요하므로

5번 부품이 가진 모든 기본 부품의 2배가 필요하다.

따라서,

7번 부품의 경우

[기본 부품 1 : 4개, 기본 부품 2 : 4개] 가 된다.

...

이런 식으로 위상 정렬을 수행하면서

이전 부품이 가진 기본 부품의 수와 필요한 이전 부품의 수를 곱하여 다음 부품에 기본 부품 개수 정보를 넘기는 방식을 사용하면

최종 부품의 기본 부품 정보를 파악할 수 있게 된다.

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int M = Integer.parseInt(br.readLine());
        int[] indegree = new int[N + 1];

        Part[] parts = new Part[N + 1];
        for (int i = 0; i <= N; i++) {
            parts[i] = new Part(i);
        }

        for (int i = 0; i < M; i++) {
            String[] input = br.readLine().split(" ");
            int next = Integer.parseInt(input[0]);
            int pre = Integer.parseInt(input[1]);
            int numOfPre = Integer.parseInt(input[2]);
            indegree[next]++;
            parts[pre].nextParts.put(next, numOfPre);
        }

        Queue<Integer> q = new LinkedList<>();
        for (int i = 1; i <= N; i++) {
            if (indegree[i] == 0) {
                q.offer(i);
                // 기본 부품을 이루는 기본 부품은 자기 자신 1개
                parts[i].defaultParts.put(i, 1);
            }
        }

        // 위상정렬
        while (!q.isEmpty()) {
            int idx = q.poll();
            Part part = parts[idx];

            for (int nextIdx : part.nextParts.keySet()) {
                Part next = parts[nextIdx];
                int numOfPrePart = part.nextParts.get(nextIdx);

                // 이전 부품의 기본 부품들을 다음 부품에 기록
                for (int idxOfDefaultPart : part.defaultParts.keySet()) {
                    int numOfDefaultPart = part.defaultParts.get(idxOfDefaultPart);
                    next.defaultParts.put(idxOfDefaultPart, next.defaultParts.getOrDefault(idxOfDefaultPart, 0) + numOfPrePart * numOfDefaultPart);
                }

                // 만약 이전 부품이 다 체크되었다면 큐에 추가
                indegree[nextIdx]--;
                if (indegree[nextIdx] == 0) {
                    q.offer(nextIdx);
                }

            }
        }

        Part toy = parts[N];

        List<int[]> ans = new ArrayList<>();
        for (Integer defaultPart : toy.defaultParts.keySet()) {
            ans.add(new int[]{defaultPart, toy.defaultParts.get(defaultPart)});
        }

        Collections.sort(ans, (a, b) -> a[0] - b[0]);

        StringBuilder sb = new StringBuilder();
        for (int[] info : ans) {
            sb.append(info[0] + " " + info[1] + "\n");
        }
        System.out.println(sb);

    }

    static class Part {
        int idx;
        Map<Integer, Integer> nextParts = new HashMap<>();

        Map<Integer, Integer> defaultParts = new HashMap<>();

        public Part(int idx) {
            this.idx = idx;
        }

    }
}

 

결과