[백준 24115번] 地域 (Regions)

 

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

 

일본의 알고리즘 문제들(특히 JOI)을 찾아보면 재밌는 것들이 많다.

 

이 문제도 내가 재밌게 풀었던 문제 중 하나이다.

 

해당 문제는 한국어 번역이 존재하지 않기 때문에 문제에 대한 번역을 같이 올리려고 한다.

 

문제

JOI국에는 $1$부터 $N$까지의 번호가 붙어 있는 $N$개의 도시가 있다. 이 도시들은 양방 통행 가능한 길을 통해 트리 형태로 연결되어 있다. 즉, 임의의 두 도시는 길을 통해 왕래가 가능하며, 그 경로는 하나뿐이다. 길은 총 $N-1$개 존재한다.

이제 도시를 $M$개의 지역으로 나눌 것이다. 모든 지역은 한 개 이상의 도시를 포함하며, 모든 도시는 $1$개의 지역에 포함되어야만 한다. 또한, 같은 지역에 포함되어 있는 임의의 $2$개의 도시는 그 지역에 포함되지 않은 도시를 거치지 않고 왕래가 가능해야 한다.

각 지역의 직경의 최댓값 $d_{max}$가 최소가 되도록 지역을 나누고 싶다. 이때, 지역의 직경이라 함은 그 지역에 포함된 $2$개의 도시 간의 거리의 최댓값이다. $2$개의 도시 간의 거리라고 함은 $2$개의 도시를 연결하는 경로에 포함된 도로의 길이의 합이다. 지역이 한 개의 도시만을 포함하는 경우, 그 지역의 직경은 $0$이다.

입력

표준 입력으로 아래의 입력을 받는다.
첫 번째 줄에 정수 $N$, $M$이 공백으로 구분되어 주어진다.
이어서 $N-1$개의 줄에 거쳐 한 줄에 하나의 길에 대한 정보가 주어진다. $i$번째 줄은 $i$번 길에 대해서 설명하며, 정수 $A_i$, $B_i$, $C_i$가 공백으로 구분되어 주어진다.

출력

표준 출력으로 $d_{max}$의 최솟값을 하나의 정수로 출력한다.

제한

● $2 \leq N \leq 30,000$이며, $N$은 도시의 개수
● $2 \leq M \leq N$이며, $M$은 지역의 개수
● $1 \leq A_i \lt B_i \leq N$이며, $A_i$와 $B_i$는 $i$번 길로 연결된 $2$개의 도시
● $1 \leq C_i \leq 100$이며, $C_i$는 길 $i$의 길이

 

제한을 보면 $N \times C_i$는 $3,000,000$ 이하이다.

 

이는 직경이 최대 $3,000,000$임을 뜻한다.

 

즉, 직경의 최댓값을 이분탐색(매개 변수 탐색)하면서 최대 분할 가능한 횟수 $M-1$를 초과하지 않는 $d_{max}$의 최솟값을 찾으면 시간 내에 정답을 구할 수 있다.

 

직경의 최댓값을 $d_{max}$라고 할 때, 직경이 $d_{max}$를 초과할 때마다 가장 거리가 먼 노드를 연결하는 간선부터 분할하기를 반복해주면 된다.

 

이때, 직경은 $($가장 거리가 먼 노드까지의 거리$)+($그 다음으로 거리가 먼 노드까지의 거리$)$로 계산할 수 있다.

 

예를 들어, 아래와 같은 부분 트리를 빨간 점 위치에서 탐색 중일 때, $d_{max} = 10$이라면

직경이 $18$로 $d_{max}$를 초과했으므로 아래와 같이 거리가 가장 먼 노드와의 연결부터 차례대로 끊어버릴 것이다.

이제 직경이 $9$로 $d_{max}$를 초과하지 않으므로 가장 거리가 먼 노드와의 거리($6$)를 리턴해주면 된다.

 

주의할 점은 부모 노드에게 필요한 정보는 부모 노드 기준 가장 거리가 먼 노드까지의 거리이므로, 직경은 $($가장 거리가 먼 노드까지의 거리$)+($그 다음으로 거리가 먼 노드까지의 거리$)$로 구하지만, 리턴할 때는 가장 거리가 먼 노드까지의 거리만 리턴해야한다는 것이다.

 

#include<iostream>
#include<algorithm>
#include<vector>
#define pii pair<int, int>
using namespace std;
int n, m, cnt = 0;
vector <pii> tree[30001];//連結情報と間の距離
bool cmp(int a, int b) {
	return a > b;
}
int dp(int num, int bf, int h) {//h==最大分割の制限
	vector <int> d;

	for (int i = 0; i < tree[num].size(); i++) if (tree[num][i].first != bf) {
		int re = dp(tree[num][i].first, num, h) + tree[num][i].second;

		d.push_back(re);
	}
	d.push_back(0);
	d.push_back(0);
	int i = 0;
	sort(d.begin(), d.end(), cmp);
	for (; d[i]; i++) {
		if (d[i] + d[i + 1] <= h) break;
		cnt += 1;
	}
	return d[i];
}
bool d(int num) {
	cnt = 0;
	dp(1, 0, num);
	if (cnt > m) return 0;
	else return 1;
}
int main() {
	int l = 0, r = 0, t;

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

		cin >> a >> b >> c;
		tree[a].push_back({ b, c });
		tree[b].push_back({ a, c });
		r += c;
	}
	while (l < r) {
		t = (l + r) / 2;
		if (d(t)) r = t;
		else l = t + 1;
	}
	cout << r;
}