[백준 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(3 ≤ N ≤ 100)이 주어지는데, 1부터 N-1까지는 기본 부품이나 중간 부품의 번호를 나타내고, N은 완제품의 번호를 나타낸다. 그리고 그 다음 줄에는 자연수 M(3 ≤ M ≤ 100)이 주어지고, 그 다음 M개의 줄에는 어떤 부품을 완성하는데 필요한 부품들 간의 관계가 3개의 자연수 X, Y, K로 주어진다. 이 뜻은 “중간 부품이나 완제품 X를 만드는데 중간 부품 혹은 기본 부품 Y가 K개 필요하다”는 뜻이다. 두 중간 부품이 서로를 필요로 하는 경우가 없다.

출력

하나의 완제품을 조립하는데 필요한 기본 부품의 수를 한 줄에 하나씩 출력하되(중간 부품은 출력하지 않음), 반드시 기본 부품의 번호가 작은 것부터 큰 순서가 되도록 한다. 각 줄에는 기본 부품의 번호와 소요 개수를 출력한다.

정답은 2,147,483,647 이하이다.

알고리즘

위상정렬

접근 방식 및 풀이

기본 부품을 구별한다.

해당 문제는 완제품을 조립하는데 필요한 기본 부품의 개수만 필요하다. 중간 부품의 개수는 필요하지 않기 때문에 우선 기본 부품을 구별해낼 필요가 있다. 어떤 부품이 기본 부품인지는 어떻게 알 수 있을까? 이는 제공되는 조립법을 통해서 알 수 있다. 기본 부품은 조립법에서 재료로만 등장할 수 있기 때문이다. 결국 재료법에서 조합품으로 한번도 등장하지 않는 것이 기본 부품이다.

기본 부품을 구별해냈으니 이제 완제품을 위해 필요한 기본 부품들의 개수의 계산을 본격적으로 시작하자.

위상정렬을 통해 기본 부품부터 차례차례 계산한다.

위상정렬은 간단히 설명하면 그래프에서 꼭짓점들을 변의 방향을 거스르지 않도록 나열하는 것을 말한다. 이 문제의 경우 부품이 꼭짓점으로, 조립법을 통해 알 수 있는 부품간의 관계가 변과 변의 방향으로 생각하여 위상정렬을 사용할 수 있다.

그런데 계산을 하려고 보니 고민이 생겼다.

‘기본 부품부터 완제품으로 올라가면서 계산해야할까? 아니면 완제품부터 기본 부품으로 내려가면서 계산해야할까?’하는 고민이었다. 필자의 경우 아래에서부터 위로 올라가는 것이 구현하기 더 편할 것 같아서 해당 방법을 선택했다.

먼저, 기본 부품이 재료로 등장하는 모든 조립법을 찾는다. 해당 조립법을 통해서 몇몇 중간 부품들을 기본 부품만으로 표현할 수 있게 된다. 예를 들어 설명해보겠다.

1번, 2번을 기본 부품, 3번을 중간 부품이라고 생각해보자. 또한 조립법에는 ‘3번 부품은 1번 부품 4개 필요’, ‘3번 부품은 2번 부품 3개 필요’라고 적혀있다고 가정하자. 이 경우 3번 부품을 4개의 1번 부품과 3개의 2번 부품 (3번 = 4 x 1번 + 3 x 2번) 으로 표현할 수 있게 된다.

이런식으로 몇몇 중간 부품들이 기본 부품만으로 표현할 수 있게 되면, 해당 중간 부품들이 재료로 등장하는 모든 조립법을 찾고 다시 위와 같은 과정을 반복한다. 이 과정을 거치면 더 상위의 중간 부품들도 기본 부품으로 표현할 수 있게 된다. 말이 어려우니 다시 예를 들어 설명해보겠다.

이전 예시에서 중간 부품 4번과 ‘4번 부품은 3번 부품 2개 필요’라는 조립법도 추가로 존재한다고 생각해보자. 이 경우 우리는 이미 3번 부품이 4개의 1번 부품과 3개의 2번 부품 (3번 = 4 x 1번 + 3 x 2번) 이라는 것을 알고 있기에 4번 부품이 8개의 1번 부품과 6개의 2번 부품(4번 = 2 x 3번 = 2 x (4 x 1번 + 3 x 2번) = 8 x 1번 + 6 x 2번)이라는 것을 알아낼 수 있다.

해당 과정을 계속해서 반복하면 결국에는 완제품도 기본 부품만으로 표현할 수 있게 된다.

코드

문제 풀이에 사용한 언어: C

#include <stdio.h>

int
main(){
    int n, m, to, from, num, base_num = 0;
    int array[101][101] = {0,};
    int queries[101][3] = {0,}; // 부품 조립법
    int count[101] = {0,};
    /* to에 등장하는 횟수를 계산하기 위한 배열,
     count가 0일 경우 해당 부품이 기본 부품만으로 표현할 수 있게 된 상태,
     count가 -1일 경우 해당 부품에 대한 계산이 끝난 상태 */
    int base[101] = {0,};
    
    scanf("\n%d\n%d\n", &n, &m);
    
    for(int i = 0; i < m; i++){
        scanf("\n%d %d %d\n", &to, &from, &num);
        queries[i][0] = to; // 중간 부품이나 완제품
        queries[i][1] = from; // 중간 부품 혹은 기본 부품
        queries[i][2] = num; // 필요한 개수
        count[to]++; // 등장 횟수 늘리기
    }
    for(int i = 1; i <= n; i++){
        if(count[i] == 0){ // 한번도 to에 등장하지 않았다면 기본 부품
            array[i][i] = 1; // 기본 부품을 만들기 위한 기본 부품 수는 1이다.
            base[base_num++] = i; // base 배열에 해당 부품 저장
        }
    }
    while(count[n] != -1){ // 완제품에 대한 계산이 끝날 때까지 반복
        for(int i = 1; i <= n; i++){ // 모든 부품에 대해서
            if(count[i] == 0){ // count가 0이면, 해당 부품이 기본 부품만으로 표현할 수 있게 된 상태이기 때문에 해당 부품의 상위 부품에 대한 계산을 시작한다.
                for(int j = 0; j < m; j++){
                    if(queries[j][1] == i){ // 해당 부품을 재료로 하는 상위 부품들을 찾는다.
                        for(int k = 0; k < base_num; k++){ // 모든 기본 부품들에 대하여
                            array[queries[j][0]][base[k]] += queries[j][2] * array[queries[j][1]][base[k]]; // 상위 부품을 만들기 위한 기본 부품 수 += 상위 부품을 만들기 위해 필요한 현재 부품 수 * 현재 부품을 만들기 위해 필요한 기본 부품 수
                        }
                        count[queries[j][0]]--; // 해당 쿼리에 대한 계산을 끝냈기 때문에 상위 부품의 등장 횟수를 줄인다.
                    }
                }
                count[i] = -1; // 해당 부품에 대한 계산 완료
            }
        }
    }
    for(int i = 0; i < base_num; i++){
        if(array[n][base[i]] != 0){
            printf("%d %d\n", base[i], array[n][base[i]]);
        }
    }
    return 0;
}