백준 검역소(13209)

검역소

이번 카카오 코테 5번 문제로 이와 유사한 문제가 출제되었다. (이진 트리이고, 범위가 작은것만 다름)

1. 힌트

1) 어떤 한 사람이 감염될 경우 감염될 수 있는 사람은 그 사람이 사는 도시에 있는 사람들과, 그 도시에 검역소 없이 연결된 도시에 사는 사람들이다.

2) 일반적인 해법을 찾기 어렵기 때문에, 결국 모든 경우를 시도해볼 수 밖에 없다. 만약 한 그룹에 최대로 담을 수 있는 정점의 가중치의 합이 정해진다면 그리디한 해법으로 풀 수 있다.

3) $f(x) =$ 한 그룹의 가중치의 합이 $x$가 넘지 않게 담았을 때, 검역소가 $K$개가 넘지 않게 담을 수 있는지 여부. 이렇게 정의하면 $f(x)$는 단조 증가 함수이므로 이분 탐색이 가능하다.

2. 접근

1) 비슷한 문제를 풀어본 적이 있던가?

기타 레슨

기타 레슨 문제는 블루레이의 크기를 최소한으로 해서 모든 레슨을 담는 문제다. 이 문제 또한 "전염병이 퍼질 경우에 대비해 정부에서 비축해야 하는 치료제의 개수"는 검역소로 나눠 놓은 그룹들 중에서 가장 큰 그룹의 인구수의 합이기 때문에, 가장 큰 그룹의 인구수 합이 최소가 되도록 $K$개의 검역소를 설치할 때, 가장 큰 그룹의 인구수 합은 얼마인지를 묻는 문제가 된다.
기타 레슨 문제는 한번에 문제의 답을 구하는 해법을 찾기는 어렵지만, 만약 블루레이의 크기가 주어진다면 담을 수 있는지 여부를 찾기는 쉬웠기 때문에 이를 이용해 이분 탐색을 더해서 풀었다.
이 문제도 가능할까?

2) 문제를 분해할 수 있을까?

어느 두 도시도 오직 하나의 경로로만 통행할 수 있다고 했기 때문에, 문제에서 주어지는 도시들은 트리임을 알 수 있다.
트리는 재귀적인 성질을 띄고 있기 때문에 문제를 분해할 수 있더. 어떤 정점을 기준으로 자신의 자식들을 담는다고 생각할 때, 모두 담은다음에 가장 큰 것부터 끊어가는식으로 최적해를 구할 수 있다. 다음과 같이 탐욕적 선택 속성을 증명할 수 있다. $p$는 현재 자식을 끊어내려는 정점이고 $c$는 자식들이다.

우선 담을 수 있다면 최대한 담는것이 이득이라는 것을 증명해보자. 만약 어떤 최적해가 최대한 담지 않는 방식으로 위와 같이 만들어졌다고 가정해보자. $p$가 속한 그룹은 사실 $c1$과 $c2$를 모두 담을 수 있지만 끊어놨다.

끊어놓은 것을 그냥 잇는 해로 바꾸더라도 $K$는 줄어들기 때문에 무조건 이득이다.
그렇다면 가장 큰 것부터 끊어주는 것이 최적해라는 것은 어떻게 증명할 수 있을까?
마찬가지로 어떤 최적해가 큰 것부터 끊어주는 것이 아닌 방식으로 만들어졌다고 하자.

$c1$보다 $c2$가 속하는 그룹의 인구수가 더 크지만 $c1$을 끊어주었다. 이렇게 선택했는데 최적해였다고 하자

그 최적해를 이와같이 더 작은 쪽을 포함하게 바꿀 수 있다.
$p$가 속한 그룹은 원래의 답보다 인구수가 작아지므로 $c1$으로 바꿀 수 있고, $c2$또한 마찬가지다.
이렇게 답을 바꾸더라도 절대로 손해를 보지는 않는다.

3. 구현

public class Main {
	static int[] S; static long M;
	static ArrayList<ArrayList<Integer>> adj;
	static int cnt;
	
	// here 루트로 하는 트리를 정점의 가중치의 합이 M을 넘지 않게
	// 최적의 방법으로 나누고 here이 속한 그룹의 가중치의 합을 반환
	static long postorder(int here, int parent) {
		long sum = S[here];
		PriorityQueue<Long> pq = new PriorityQueue<>(Collections.reverseOrder());
		for (int there : adj.get(here)) {
			if (there == parent) continue;
			long t = postorder(there, here);
			sum += t; pq.offer(t);
		}
		// 어차피 끊어내야 한다면 큰거부터 끊어낸다
		while (!pq.isEmpty() && sum > M) { sum -= pq.poll(); cnt++; }
		return sum;
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder ans = new StringBuilder();
		int TC = Integer.parseInt(br.readLine());
		while (TC-- > 0) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			int N = Integer.parseInt(st.nextToken());
			int K = Integer.parseInt(st.nextToken());
			S = new int[N + 1];
			st = new StringTokenizer(br.readLine(), " ");
			for (int i = 1; i <= N; i++) S[i] = Integer.parseInt(st.nextToken());
			adj = new ArrayList<>(N);
			for (int i = 0; i <= N; i++) adj.add(new ArrayList<>());
			for (int i = 0; i < N - 1; i++) {
				st = new StringTokenizer(br.readLine(), " ");
				int u = Integer.parseInt(st.nextToken());
				int v = Integer.parseInt(st.nextToken());
				adj.get(u).add(v); adj.get(v).add(u);
			}
			// f(x) = 한 그룹의 가중치의 합이 x가 넘지 않게,
			// 최적의 방법으로 잘랐을 때 자르는 횟수가 K를 넘지 않게 자를 수 있는지 여부
			// f(lo) = false f(hi) = true인 hi를 반환
			long lo = 0; long hi = 100000000000000L;
			int max = 0;
			for (int i = 1; i <= N; i++) max = Math.max(max, S[i]);
			while (lo + 1 < hi) {
				long mid = (lo + hi) / 2;
				M = mid; cnt = 0;
				postorder(1, 1);
				if (max <= mid && cnt <= K) hi = mid;
				else lo = mid;
			}
			ans.append(hi).append("\n");
		}
		System.out.print(ans);
	}
	
}

1) 시간 복잡도

트리의 순회 과정은 정확하게 정점을 한 번씩만 방문하기 때문에 총 $N$번을 방문하게 되고, 인접 간선은 $N - 1$번 검사하고 검사할 때 마다 $lgN$의 우선순위큐에 대한 삽입이 이루어진다. 끊어내는 과정 또한 아무리 많이 끊어봐야 간선의 개수보다 많이 끊을 순 없다.
이분 탐색의 상한은 $10^{14}$이므로 $N \times lgN \times lg10^{14}$

2) 테스트 케이스