[백준/BOJ] 백준 2197번 : 분해 반응

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

2197번: 분해 반응

루트가 1번 노드인 트리를 만들고, 리프 노드부터 위로 올라가면서 cache[노드][크기]에 해당 노드가 루트인 서브 트리에서 해당 크기로 만드는데 최소로 자르는 횟수를 채운 뒤, 모든 노드를 확인하며 각 노드에서 크기 m을 만드는데 자르는 최소 횟수 중 가장 작은 값을 찾는 방법으로 문제를 해결했다. 각 노드의 cache를 채울 때 해당 노드의 자식 노드를 이용했는데, 자식 노드에서 이미 만들어진 cache와 자신이 가지고 있는 cache를 조합해서 자신의 cache를 업데이트해 나아갔다. 이때 주의해야 될 점은 어떤 자식 노드로 자신의 cache를 업데이트해 나아가는 중에 현재 업데이트하고 있는 해당 노드의 cache정보를 현재 업데이트에 사용하지 않도록 주의해야 한다. 이를 방지하기 위해 현재 노드의 큰 크기의 cache 정보부터 업데이트해 나아갔다. (큰 크기의 cache는 작은 크기의 cache정보를 업데이트하는 데 사용되지 않기 때문)

 

코드

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

int n, m;
vector<int> adj[155];
vector<int> visited(155, 0);
vector<int> children[155];
vector<int> parent(155, 0);
vector<int> tree_size(155, 0); //해당 정점이 루트인 서브트리의 크기
vector<vector<int>> cache(155, vector<int>(155, 987654321)); //[정점][크기] = 해당정점이 루트인 서브트리에서 해당 크기로 만드는데 최소 자르는 횟수
vector<int> order;

void MakeTree(int here) {

	visited[here] = 1;
	tree_size[here]++;

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

		if (visited[there])
			continue;

		MakeTree(there);

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

void MakeOrder(int start) {
	queue<int> q;
	q.push(start);

	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);
		}
	}
}

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

	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);
	MakeOrder(1);
	reverse(order.begin(), order.end());

	//리프노드 부터 위로 가면서 확인한다
	for (int a = 0; a < order.size(); a++) {

		int here = order[a];

		cache[here][1] = children[here].size(); //자신 노드 모두 끊기
		cache[here][tree_size[here]] = 0; //아무것도 끊지 않는 경우

		//리프노드일때
		if (children[here].size() == 0)
			continue;

		//here노드의 cache 채우기
		//각 자식노드를 이용
		for (int i = 0; i < children[here].size(); i++) {
			int there = children[here][i]; //here의 자식 노드

			for (int j = tree_size[here]; j >= 1; j--) { //지금 업데이트하는것을 지금 업데이트하는곳에 사용하지 않기위해 큰것부터 채우기

				//cache[here][j]만들기
				for (int k = 1; k < j; k++) { //이전에서 k개 고르고, there에서 j-k개 고르는 경우

					if (cache[here][k] == 987654321) //이전에 k가 계산된적이 없을때
						continue;

					if (tree_size[there] >= j - k) //there에서 j-k개를 고를 수 있을때
						cache[here][j] = min(cache[here][j], cache[here][k] + cache[there][j - k] - 1);
				}
			}
		}

	}

	int result = 987654321;
	for (int i = 1; i <= n; i++) {

		//루트 노드일때
		if (i == 1)
			result = min(result, cache[i][m]);

		//루트 노드가 아닐때 (부모로 가는 간선도 하나 잘라야 된다)
		else
			result = min(result, cache[i][m] + 1);
	}
	cout << result;

	return 0;
}