장난감 조립 (feat. 백준, 2637번)

장난감 조립
https://www.acmicpc.net/problem/2637

2637번: 장난감 조립

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <vector>
#include <queue>
#include <set>
#include <algorithm>
using namespace std;
vector<pair<int, int>> arr[101];
int check[101]{0};
int cnt[101]{0};
int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
    register int N, M;
    cin >> N >> M;
    for(register int m = 0, x, y, k; m < M; ++m){
        cin >> x >> y >> k;
        arr[x].push_back(make_pair(y, k));
        ++check[y];
    }
    set<int> ans;
    queue<int> q;
    q.push(N);
    cnt[N] = 1;
    while(!q.empty()){
        auto current = q.front(); q.pop();
        if(arr[current].empty())
            ans.insert(current);
        for(auto& p : arr[current]){
            auto next = p.first, value = p.second;
            cnt[next] += cnt[current] * value;
            if(--check[next] == 0)
                q.push(next);
        }
    }
    // sort(ans.begin(), ans.end());
    for(auto& v : ans)
        cout << v << ' ' << cnt[v] << '\n';
	return 0;
}
// *&)*@*

 

반응형

위상 정렬을 이용하는 문제입니다.

문제로 주어진 N이 완제품이 되는 기준이므로 N이 필요로 하는 중간 부품(Y) 와 개수(K개) 에 대해 거꾸로 찾아가는 형태입니다.