백준) 2637 장난감조립

장난감조립

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

완제품을 조립하기위해 기본 부품들과 기본 부품들로 만드는 중간 부품들이 필요하다.

기본->중간 // 중간->중간 // 중간->완제품 으로 만들기 위해 필요한 개수가 주어질 때,

완제품을 만들기 위해 필요한 기본 부품들의 갯수를 구해보자.

테크트리를 탄다는 점에서 위상정렬을 생각해 볼 수 있다.

또한 부품을 여러개 써야 다음 단계로 넘어갈 수 있다는 점에서, 간선에 그 몇개에 해당하는 정보도 저장해야 한다.

그리으로 나타내면 다음과 같다.

간선을 잘 정의해서 그래프를 구성하자.

또한 각 노드마다 어떤 기본 부품이 몇개 필요한지 저장할 배열도 필요하다.

기본 부품은 진입차수가 0인 노드임을 금방 알 수 있다. 기본 부품들의 부품배열엔 자기 자신만 들어가 있을 것이다.

이제 위상정렬을 위한 큐질을 하면서 노드의 부품배열에 간선의 가중치를 전부 곱해서 다음 노드의 부품배열에 더해주자.

이후 간선을 제거해가면서 진입차수가 0이 된다면 부품이 완성된 것이고, 다음 단계로 넘어갈 수 있다. 큐에 넣는다.

#include <stdio.h>
#include <vector>
#include <queue>
using namespace std;
 
struct edge {
    int num, val;
};
int blocks[101][101];
int in[101];
int n, m, x, y, k;
 
int main() {
    scanf("%d %d", &n, &m);
    vector<vector<edge>> vec(n+1);
 
    for (int i = 0; i < m; ++i) {
        scanf("%d %d %d", &x, &y, &k);
        vec[y].push_back({ x,k });
        in[x]++;
    }
 
    queue<int> q;
    for (int i = 1; i <= n; ++i) {
        if (!in[i]) {
            q.push(i);
            blocks[i][i] = 1;
        }
    }
        
    while (!q.empty()) {
        int cur = q.front();
        q.pop();
 
        for (auto next : vec[cur]) {
            for (int i = 1; i <= n; ++i)
                blocks[next.num][i] += blocks[cur][i] * next.val;
 
            in[next.num]--;
            if (!in[next.num])
                q.push(next.num);
        }
    }
 
    for (int i = 1; i <= n; ++i)
        if (blocks[n][i])
            printf("%d %d\n", i, blocks[n][i]);
 
    return 0;
}