[백준/BOJ] 백준 2637번 : 장난감조립

www.acmicpc.net/problem/2637

2637번: 장난감조립

x를 만드는데 y가 k개 필요하다면 x에서 y로 가는 그래프 연결을 k개 만들고, n에서부터 탐색을 하여 탐색하는 부품이 기본 부품에 도달했을 때 그 부품을 체크한 백터를 반환하였다. cache를 사용해 같은 부품에 대해서 중복된 연산을 하지 않았다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int n;
int m;
vector<int> adj[101];
vector<vector<int>> cache(101, vector<int>(101, -1));

vector<int> Solve(int here)
{
	//here가 기본 부품일때
	if (adj[here].size() == 0)
	{
		vector<int> ret_temp = vector<int>(101, 0);
		ret_temp[here] = 1;

		return ret_temp;
	}

	vector<int>& ret = cache[here];

	if (ret[0] != -1)
		return ret;

	ret = vector<int>(101, 0);
	for (int i = 0; i < adj[here].size(); i++)
	{
		vector<int> temp = Solve(adj[here][i]);

		for (int j = 0; j < temp.size(); j++)
		{
			ret[j] += temp[j];
		}
	}

	return ret;
}

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

	cin >> n;
	cin >> m;

	for (int i = 0; i < m; i++)
	{
		int x, y, k;
		cin >> x >> y >> k;

		//x를 만드는데 y가 k개 필요
		for (int i = 0; i < k; i++)
		{
			adj[x].push_back(y);
		}
	}

	vector<int> result = Solve(n);

	for (int i = 0; i < result.size(); i++)
	{
		if (result[i] != 0)
			cout << i << " " << result[i] << "\n";
	}

	return 0;
}