BOJ 2637 장난감 조립

문제 링크입니다.

문제 요약

부품 별로 제작에 필요한 다른 부품의 개수가 주어집니다. 장난감을 완성하기 위해 필요한 기본 부품의 개수를 구하세요.

풀이

입력 조건으로부터 사이클이 생기지 않기 때문에 부품의 필요 관계가 DAG를 이룸을 확인할 수 있습니다. 그냥 해당 그래프를 따라가면서 각 부품 별로 필요한 기본 부품 수를 다 계산해 둔 뒤 필요할 때 끌어와서 더해 주면 됩니다.

총 시간 복잡도 ${\cal O}(N(N+M))$에 문제를 해결할 수 있습니다. 부품 수가 적어서 대충 ${\cal O}(N^3)$에 구현해도 맞을 겁니다.

코드

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

int d[123][123];
int deg[123];
bool isbasic[123];
queue<int> q;
vector<vector<int>> e;
int main(){
	cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);
	int n, m; cin >> n >> m; e.resize(n+1);
	while(m--){
		int u, v, w; cin >> v >> u >> w;
		deg[v]++;
		e[u].push_back(v);
		d[v][u] += w;
	}
	for(int i = 1; i <= n; i++){
		if(!deg[i]){
			q.push(i);
			isbasic[i] = 1;
			d[i][i] = 1;
		}
	}
	while(q.size()){
		int now = q.front(); q.pop();
		for(int i = 1; i <= n; i++) if(d[now][i] && !isbasic[i]){
			for(int j = 1; j <= n; j++) d[now][j] += d[i][j]*d[now][i];
			d[now][i] = 0;
		}
		for(auto nxt : e[now]){
			deg[nxt]--;
			if(!deg[nxt]) q.push(nxt);
		}
	}
	for(int i = 1; i <= n; i++) if(isbasic[i]) cout << i << ' ' << d[n][i] << '\n';
}