[백준/BOJ] 백준 2337번 : 트리 자르기

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

2337번: 트리 자르기

cache[151][151]에 [루트 정점][트리의 크기] = [루트 정점]이 해당 [트리의 크기]로 되는데 필요한 루트 정점 아래에서 자르는 간선의 개수를 리프 노드부터 bottom-up 방식으로 채워나간다. 이때 주의해야 될 점은 이번에 만들어진 것을 이번에 또 쓰지 않기 위해 큰 값부터 채운다.(for (int j = sub_tree_size[there]; j >= 2; j--))

 

코드

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

int n, m;
vector<int> adj[151];
int parent[151];
vector<int> children[151];
int maked[151];
int sub_tree_size[151];
int cache[151][151]; //[루트정점][트리의 크기] = [루트정점]이 해당 [트리의 크기]로 되는데 필요한 루트정점 아래에서 자르는 간선의 개수
vector<int> order;

void Pre()
{
	for (int i = 0; i < 151; i++)
	{
		parent[i] = 0;
		maked[i] = 0;
		sub_tree_size[i] = 1;

		for (int j = 0; j < 151; j++)
		{
			cache[i][j] = 987654321;

			if (j == 0)
				cache[i][j] = 0;
		}
	}
}

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);
			children[here].push_back(there);
			parent[there] = here;
			sub_tree_size[here] += sub_tree_size[there];
		}
	}

	cache[here][sub_tree_size[here]] = 0;
}

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의 부모노드

		cache[here][1] = children[here].size();
		cache[there][1] = children[there].size(); //자식노드들과 모두 끊는다고 생각

		//이번에 만들어진것을 이번에 또 쓰지 않기 위해 큰값부터 채운다
		for (int j = sub_tree_size[there]; j >= 2; j--)
		{
			//a : 부모 서브트리에서 고르는것 (1~j)
			for (int a = 1; a <= j; a++)
			{
				int b = j - a; //b : 자식 서브트리 에서 고르는것 (j-1 ~ 0)

				//해당 자식노드에서 고르는 경우일때
				if (b != 0)
				{
					cache[there][j] = min(cache[there][j], cache[there][a] + cache[here][b] - 1); // -1은 자식노드(here)와 끊은것을 다시 연결하는것
				}
			}
		}
	}

	int ret = 987654321;

	for (int i = 1; i <= n; i++)
	{
		if (i == 1) //루트노드일때
			ret = min(ret, cache[i][m]);
		else //루트노드가 아니라면 해당 노드와 부모노드와 연결된 간선을 끊어야 된다
			ret = min(ret, cache[i][m] + 1);
	}

	return ret;
}

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

	Pre();

	cin >> n >> m;

	for (int i = 0; i < n - 1; i++)
	{
		int a, b;
		cin >> a >> b;

		adj[a].push_back(b);
		adj[b].push_back(a);
	}

	MakeTree(1); //루트가 1인 트리를 만든다
	Travel(1);

	cout << Solve();

	return 0;
}