[백준/BOJ] 백준 12995번 : 트리나라

https://www.acmicpc.net/problem/12995

12995번: 트리나라

cache[서브트리의 루트번호][마을을 고를 개수]에 경우의 수 (해당 서브트리에서 해당 개수의 마을을 고르는 경우의 수)를 bottom-up 방식으로 채워나가는 방법을 통해 문제를 해결했다. sub_tree_size[there]부터 확인해야 되는데, 작은 것부터 시작하면 이번 순서에 만들어진 것을 이번 순서에 영향을 줄 수 있다(이용할 수 있다)

 

코드

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

int n, k;
vector<int> adj[51];

vector<int> parent(51, 0);
vector<int> children[51];
vector<int> sub_tree_size(51, 1);
vector<int> maked(51, 0);
vector<int> order;
vector<vector<int>> cache(51, vector<int>(51, 0));//[서브트리의 루트번호][마을을 고를 개수] = 경우의 수 (해당 서브트리에서 해당 개수의 마을을 고르는 경우의 수)

void Pre()
{
	for (int i = 0; i < 51; i++)
	{
		cache[i][1] = 1; //어떤 서브트리더라도 1개의 도시를 고르는 경우는 해당 서브트리의 루트를 고르는 하나의 경우이다
		cache[i][0] = 1;
	}
}

void MakeTree(int here)
{
	maked[here] = 1;

	for (int i = 0; i < adj[here].size(); i++)
	{
		int there = adj[here][i];

		if (maked[there] == 0)
		{
			MakeTree(there);

			parent[there] = here;
			children[here].push_back(there);
			sub_tree_size[here] += sub_tree_size[there];
		}
	}
}

void Travel(int here)
{
	queue<int> q;
	q.push(here);

	while (!q.empty())
	{
		int here = q.front();
		q.pop();

		order.push_back(here);

		for (int i = 0; i < children[here].size(); i++)
		{
			int there = children[here][i];
			q.push(there);
		}
	}

	reverse(order.begin(), order.end());
}

int Solve()
{
	//아래쪽부터 확인한다
	for (int i = 0; i < order.size(); i++)
	{
		int here = order[i];
		int there = parent[here]; //here의 부모노드

		//here가 루트노드일때
		if (there == 0)
			continue;

		//for (int j = 2; j <= sub_tree_size[there]; j++)
		//무조건 sub_tree_size[there]부터 확인해야 된다 작은것 부터 시작하면 이번순서에 만들어진것을 이번순서에 이용할 수 있다
		//bottom-up 방식으로 접근
		for (int j = sub_tree_size[there]; j >= 2; j--)
		{
			//자식노드쪽에서 a개를 고르는 경우
			for (int a = 1; a <= sub_tree_size[here]; a++)
			{
				//a는 0 ~ sub_tree_size[here]
				//a + b = j
				int b = j - a; //부모노드쪽의 서브트리에서 b개를 고른다

				if (b <= 0)
					continue;

				cache[there][j] = (cache[there][j] + (cache[here][a] * cache[there][b] % 1000000007)) % 1000000007;
			}
		}
	}

	int ret = 0;
	for (int i = 1; i <= n; i++)
	{
		ret = (ret + cache[i][k]) % 1000000007;
	}
	return ret;
}

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

	Pre();

	cin >> n >> k;

	for (int i = 0; i < n - 1; i++)
	{
		int u, v;

		cin >> u >> v;

		adj[u].push_back(v);
		adj[v].push_back(u);
	}

	MakeTree(1); //1번 정점이 루트인 트리를 만든다
	Travel(1);

	cout << Solve();

	return 0;
}