[백준/BOJ] 백준 2454번 : 트리 분할

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

2454번: 트리 분할

 

주어진 트리를 1번 정점이 루트인 트리로 만들고, 리프 노드부터 루트 노드까지 올라가면서 확인하는 노드와 해당 노드의 자식 노드 그룹이 같은 그룹으로 합쳐질 수 있는지 확인하는 방법으로 문제를 해결했다.

확인하는 정점의 자식 노드를 자식 노드가 루트인 서브 트리(자식 노드 그룹)의 크기 순으로 정렬한 뒤, 작은 것부터 확인하는 정점과 합쳐질 수 있는지를 확인하여 합쳐질 수 있으면 합치는 방식으로 문제를 해결했다. 이때 주어진 조건을 통해 확인하는 정점과 합쳐질 수 있는 직접적인 자식 노드(직접 연결된 자식 노드)는 최대 2개라는 점을 이용했다.

 

코드

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

int n, k;
vector<int> adj[300001];
vector<int> children[300001];
vector<int> maked(300001, 0);
vector<int> order;
vector<int> group_size(300001, 1);
vector<int> cut_check(300001, 0); //해당노드의 부모노드와 잘렸는지 체크
int cut_cnt = 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);
		}
	}
}

void Travle(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);
		}
	}
}

void Solve()
{
	//트리의 아래에서 위로 올라가면서 같은 경로(같은 그룹)로 합쳐지는 경우를 확인한다
	for (int i = 0; i < order.size(); i++)
	{
		int here = order[i];

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

		vector<pair<int, int>> children_group_size; //(그룹의 크기, 노드 번호)
		for (int i = 0; i < children[here].size(); i++)
		{
			int there = children[here][i];

			//해당 자식노드가 부모노드와 이미 잘려있을때
			//해당 자식노드는 고르지 못한다
			if (cut_check[there] == 1)
				continue;

			children_group_size.push_back(make_pair(group_size[there], there));
		}

		//자식노드의 그룹 크기를 정렬
		sort(children_group_size.begin(), children_group_size.end());

		//group_size[here]를 자식노드의 그룹 크기가 작은것부터 확인하여 합친다
		int add_cnt = 0; //here노드와 합쳐지는 자식노드의 개수
		for (int i = 0; i < children_group_size.size(); i++)
		{
			if (group_size[here] + children_group_size[i].first <= k + 1)
			{
				//현재 자식노드를 합친다
				group_size[here] += children_group_size[i].first;
				add_cnt++;

				//자식 노드를 최대 2개만 합칠 수 있다
				if (add_cnt == 2)
				{
					break;
				}
			}

			//더이상 자식노드를 here에 합칠 수 없을때
			else
			{
				break;
			}
		}

		//add_cnt에 포함되지 않은 here의 나머지 자식노드들은 here와 자른다
		//이때 자르는 자식노드들은 cut_check에 체크하지 않아도 되는데, 
		//이유는 here노드의 부모 노드에서 here노드의 자식노드를 쓸일이 없기 때문이다
		cut_cnt += (children_group_size.size() - add_cnt);

		//here노드가 자식노드 2개와 합쳐졌다면, 다음 부모노드에서 here노드를 사용할 수 없으므로 
		//here노드와 here노드의 부모 노드와 자른다
		if (add_cnt == 2)
		{
			//루트노드가 아닌 경우
			if (here != 1)
			{
				cut_cnt++;
				cut_check[here] = 1;
			}
		}
	}
}

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

	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번 정점이 루트인 트리를 만든다
	Travle(1); //루트에서 부터 bfs를 통해 탐색 순서를 구함

	reverse(order.begin(), order.end()); //리프 노드 부터 확인하기 위해 순서 뒤집기

	Solve();

	cout << cut_cnt + 1; //트리를 자른 횟수 + 1이 그룹의 개수

	return 0;
}