[백준] 23044. 트리 조각하기

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

요약

• 트리가 주어짐, 제거해야하는 점, 제거하면 안되는 점이 주어짐
• 폭탄을 설치하면 경로 p 미만인 점들이 삭제됨
• 조건을 만족하는 가장 큰 p의 값 구하기

접근법

• 폭탄 설치 개수의 제한은 없음
• p값이 1일때, 2일때... 판단가능
• p값이 x일때 가능한지 판단이 가능한가?
  • 제거하면 안되는 점 기준으로 거리가 x 미만인 점들에는 폭탄을 설치하면 안됨 => BFS로 구할 수 있음
  • 폭탄을 설치해도 되는 점 기준으로 거리가 p 미만인 점들은 다 삭제될 것임 => BFS로 구할 수 있음
  • 제거해야하는 점이 모두 삭제 되었는지 판단함 => 가능/불가능 판단 가능
• x의 조절을 이분탐색으로 수행함 ${O(BFS) * O(2) * O(logN) = O(NlogN) }$