장난감 조립

백준 2637번: 장난감 조립

아이디어

맨 처음에 진입차수가 없는 노드가 기본 부품이다. 기본 부품부터 시작해서 total cost를 기록한다. 큐에 넣고 돌리다 진입 차수가 0이 되는 경우, 자기 자신을 만드는데 필요한 모든 부품을 고려한 것이므로 큐에 집어넣는다. total cost 계산 방법은 다음과 같다.

while (!q.empty()) {
    int cur = q.front();
    q.pop();
    for (auto p : adj[cur]) {
        int next = p.first;
        int cnt = p.second;
        for (int i = 1; i < N+1; i++) {
            tc[i][next] += tc[i][cur]*cnt;
        }
        if (!(--indegree[next])) {
            q.push(next);
        }
    }
}

cur에서 next를 만드는 데 필요한 모든 부품은, i로 cur을 만드는데 필요한 부품 개수 * cur에서 next를 만드는데 필요한 부품 개수이다.
1번 부품부터 N번 부품까지 모두 기록하고, 이중 기본 부품만 출력해주면 된다.

코드

#include <bits/stdc++.h>

using namespace std;

constexpr int MAX = 101;
int N, M;
int indegree[MAX], tc[MAX][MAX];
bool b[MAX];
vector<vector<pair<int, int>>> adj;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> N >> M;
    adj = vector<vector<pair<int, int>>>(N+1);
    while (M--) {
        int x, y, k;
        cin >> x >> y >> k;
        adj[y].push_back({x, k}); // k개의 x가 필요하다.
        indegree[x]++;
    }

    queue<int> q;
    for (int i = 1; i < N+1; i++) {
        if (!indegree[i]) {
            q.push(i);
            b[i] = true;
            tc[i][i] = 1;
        } 
    }

    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        for (auto p : adj[cur]) {
            int next = p.first;
            int cnt = p.second;
            for (int i = 1; i < N+1; i++) {
                tc[i][next] += tc[i][cur]*cnt;
            }
            if (!(--indegree[next])) {
                q.push(next);
            }
        }
    }

    for (int i = 1; i < N+1; i++) {
        if (tc[i][N] && b[i]) {
            cout << i << ' ' << tc[i][N] << '\n';
        }
    }

    return 0;
}

여담

이렇게 한번에 계산해서 출력하면 되는데 완제품을 만드는 데 필요한 부품을 찾고 거기서 역추적하니까 MLE를 받았다.