[백준/BOJ] 백준 13209번 : 검역소

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

13209번: 검역소

이분 탐색을 이용하여 트리의 각 그룹들을 mid명 이하로 만들 수 있는지 체크하는 방법으로 문제를 해결했다. 체크하는 방법은 트리를 리프 노드에서부터 올라가면서 확인해 가며 그룹을 만들어 가는데 그룹의 인원이 가능한 최대 인원을 넘으면 최적으로 가능한 부분만 남기고 나머지는 검역소로 간선을 자르는 방법으로 나아갔다. 자른 횟수가 자를 수 있는 횟수를 넘었는지 안 넘었는지 확인하는 방식으로 문제를 해결했다.

 

코드

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

int tc;
int n, k;
vector<int> people(100001);
vector<int> adj[100001];

vector<int> parent(100001);
vector<int> children[100001];
vector<int> maked(100001); //트리가 만들어진 노드인지 체크

vector<int> order;

void Pre()
{
	for (int i = 0; i < 100001; i++)
	{
		people[i] = 0;
		adj[i].clear();

		parent[i] = 0;
		children[i].clear();
		maked[i] = 0;
	}

	order.clear();
}

//here가 루트인 서브트리를 만든다
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);
		}
	}
}

//트리를 bfs로 순환하면서 순서를 구한다
void Travel(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);
		}
	}

	//순서를 뒤집는다
	reverse(order.begin(), order.end());
}

//able_cut : 트리를 자를 수 있는 횟수
//max_group : 트리를 잘랐을때 가능한 그룹 인원의 최대
bool Check(long long max_group, int able_cut)
{
	vector<long long> sub_sum(100001, 0); //해당 정점이 루트인 그룹의 사람 수

	int cut_cnt = 0;

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

		//리프노드일때
		if (children[here].size() == 0)
		{
			sub_sum[here] = (long long)people[here];
		}

		else
		{
			//해당 그룹이 max_group을 넘지 않게 체크하는것
			long long check_sum = people[here];
			sub_sum[here] = check_sum;

			vector<pair<long long, int>> sub_sum_there; //(sub_sum값, 도시 번호)
			for (int j = 0; j < children[here].size(); j++)
			{
				int there = children[here][j];

				sub_sum_there.push_back(make_pair(sub_sum[there], there));
			}

			sort(sub_sum_there.begin(), sub_sum_there.end());
			for (int j = 0; j < sub_sum_there.size(); j++)
			{
				if (check_sum + sub_sum_there[j].first <= max_group)
				{
					check_sum += sub_sum_there[j].first;

					sub_sum[here] = check_sum;
				}

				//max_group의 크기를 넘었을때 그 외의 there은 모두 검역소로 잘라야 된다
				else
				{
					cut_cnt += (sub_sum_there.size() - j);

					break;
				}
			}
		}
	}

	if (cut_cnt > able_cut)
		return false;

	return true;
}

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

	cin >> tc;

	for (int t = 0; t < tc; t++)
	{
		Pre();

		cin >> n >> k;

		int max_people = -1;
		for (int i = 1; i <= n; i++)
		{
			int x;
			cin >> x;

			people[i] = x;
			max_people = max(max_people, people[i]);
		}

		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); //트리를 순환하여 순서를 구한다 (구한 순서는 뒤집어서 밑에서 부터 올라가는 풀이로 사용된다)

		long long left = max_people;
		long long right = 100000000000000;
		long long result = -1;

		while (left <= right)
		{
			long long mid = (left + right) / 2;

			//트리의 각 그룹들을 mid명 이하로 만들 수 있는지 확인
			if (Check(mid, k) == true)
			{
				result = mid;
				right = mid - 1;
			}

			else
			{
				left = mid + 1;
			}
		}

		cout << result << "\n";
	}

	return 0;
}