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

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

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

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

코드

#include #include #include #include #include using namespace std; int n, m; vector adj[151]; int parent[151]; vector children[151]; int maked[151]; int sub_tree_size[151]; int cache[151][151]; //[루트정점][트리의 크기] = [루트정점]이 해당 [트리의 크기]로 되는데 필요한 루트정점 아래에서 자르는 간선의 개수 vector 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 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; }

from http://geniusjo-story.tistory.com/500 by ccl(A) rewrite - 2021-09-01 14:00:18