[BOJ 19669] Firefighting

문제: https://www.acmicpc.net/problem/19669

풀이:

degree가 $1$인 노드 $u$를 생각합시다. 해당 노드에 소방서를 놓는 것과 해당 노드랑 바로 인접한 간선 $v$에 소방서를 놓는 것을 생각해보면, $u$를 제외한 다른 모든 정점은 $v$에 소방서를 놓는 것이 더 가깝습니다. 만약 $v$에 소방서를 놓은 이후 길이가 $w (\le K)$인 도로를 따라 $u$로 올 수 있다면, $u$에는 굳이 소방서를 놓을 필요가 없습니다. 이 경우에는 $v$와 $K-w$ 거리 이내에 있는 소방서가 있는 것으로 충분합니다.

이 관찰을 확장해서 정점 $i$가 거리 $R_i$ 이내의 소방서를 필요로 한다고 해 봅시다. degree가 $1$ 인 노드 $u$와 길이 $w$의 도로로 인접한 노드 $v$에 대해

• $R_u \ge w$: $u$에 소방서를 놓지 않아도 되며, $v$에 거리 $R_u - w$ 이하의 소방서를 놓아야 합니다. 그러므로 $R_v$ 를 $\min(R_v, R_u - w)$ 로 바꾸어도 같은 상황입니다.
• $R_u < w$: $u$에 소방서를 놓아야 합니다.

이제 $u$에 소방서를 놓는 경우를 신중하게 생각해야 합니다. $u$에 소방서가 놓인 이후 해당 소방서에서 거리가 $K$ 이내인 정점을 모두 삭제하는 방법을 우선 생각해 볼 수 있습니다. 하지만 이는 틀린 접근입니다. 삭제된 정점이 사용 불가능 한 것이 아닌, 다른 소방서가 지어졌을 때 해당 정점을 지나갈 수도 있기 때문입니다.(조금 더 써 보면, 해당 노드의 degree가 $1$이 아니기 때문입니다.) 그래서 우리는 하나의 변수를 더 도입할 것입니다. 정점 $i$에서 가장 가까운 소방서의 길이를 $H_i$라고 합시다. 이 경우, 위 조건은 다음과 같이 바뀝니다.

• $R_u < H_u$인 경우:
  • $R_u \ge w$: $u$에 소방서를 놓지 않아도 되며, $v$에 거리 $R_u - w$ 이하의 소방서를 놓아야 합니다. 그러므로 $u$노드를 제외한 후 $R_v$ 를 $\min(R_v, R_u - w)$ 로 바꾸어도 같은 상황입니다.
  • $R_u < w$: $u$에 소방서를 놓아야 합니다. $H_u = 0$으로 바꿉니다.
• $R_u \ge H_u$인 경우: 이미 $u$번째 노드는 조건을 만족하므로, 추가적으로 연산을 해 줄 필요가 없습니다. 노드를 안전하게 제거해도 됩니다.

위 처리를 한 이후, $H_v$ 를 $\min(H_v, H_u+w)$로 바꿔야 합니다.(소방서의 위치를 업데이트 해 줍니다.)

문제의 상황은 처음에 모든 $i$에 대해 $R_i = K, H_i = \infty$로 생각한 것이므로, 이 조건 하에서 위 처리를 BFS 혹은 위상정렬과 유사한 방식으로 진행하면 됩니다.

마지막으로, $N=1$인 경우의 처리를 조심하도록 합시다.

구현: https://www.acmicpc.net/source/share/b621b109d0cf4c7baa8afe2d6695e541