장난감 조립 2637

문제

접근 방법

위상 정렬로 가장 낮은 단계에 부품에서부터 점차 올라가면 된다.
해당 부품을 만드는 데 또 다른 부품이 필요하다면 중간 부품이라는 점을 이용해서 중간 부품이면 중간 부품을 이루는 기본 부품의 개수를, 기본 부품이면 그 자체의 개수를 상위 부품의 필요 개수에 더해주면 된다.

코드

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    int N, M, X, Y, K;
    cin >> N >> M;
    vector<vector<pair<int, int>>> graph(N + 1, vector<pair<int, int>>());
    vector<vector<int>> cost(N + 1, vector<int>(N + 1));
    vector<int> inDegree(N + 1);
    queue<int> q;
    bool isMid;
    while (M--)
    {
        cin >> X >> Y >> K;
        ++inDegree[X];
        graph[Y].push_back({X, K});
    }
    for (int i = 1; i <= N; ++i)
    {
        if (!inDegree[i] && !graph[i].empty())
            q.push(i);
    }
    while (!q.empty())
    {
        int cur = q.front();
        q.pop();
        isMid = false;
        for (int i = 1; i <= N; ++i)
            if (cost[cur][i])
            {
                isMid = true;
                break;
            }
        for (auto next : graph[cur])
        {
            if (isMid)
                for (int i = 1; i <= N; ++i)
                {
                    cost[next.first][i] += cost[cur][i] * next.second;
                }
            else
            {
                cost[next.first][cur] = next.second;
            }
            if (!(--inDegree[next.first]))
            {
                q.push(next.first);
            }
        }
    }
    for (int i = 1; i < N; ++i)
    {
        if (cost[N][i])
            cout << i << " " << cost[N][i] << "\n";
    }
    return 0;
}

풀이

중간 부품인지 기본 부품인지에 따라 처리를 다르게 했다. 기본 부품이면 그대로 다음 부품값에 들어가고 중간 부품이면 반복문으로 구성하는 기본 부품들을 계승시켜주었다.
중간 부품이 기본 부품보다 무조건 큰 번호를 가진다는 보장이 없으므로 반복문을 N-1번까지 돌려서 기본 부품인지 중간 부품인지 확인했다.