문제

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

해설

바이러스가 최대한 덜 퍼지도록 연구소에 벽을 3개 세워서 안전 영역의 최대 크기를 구하는 문제입니다. 바이러스가 퍼지는 과정은 BFS를 사용하면 됩니다.

시간복잡도 계산

$3 \leq N, M \leq 8$에서 N*M 크기의 연구소에 벽을 3개 세우는데 $(N \times M)^3$가 소요되고 바이러스가 퍼지는데 $N \times M$가 걸리므로, 최대 uptime은 $(N \times M)^3 \times N \times M \leq 10^{18}$ 입니다. 따라서 단순히 BFS와 Brute-force를 사용할 수 있습니다.

구현

입력을 받을 때, 바이러스의 위치는 따로 저장해 둡니다.

Brute-force로 가능한 모든 위치에 벽을 세웁니다. 이 때, 세웠던 벽을 다시 없애는 부분에 주의해야 합니다.

바이러스의 위치에서부터 BFS로 상하좌우 4방향으로 이동합니다. 이 때, 아직 방문하지 않은 위치에 도착했다면 안전 영역의 범위를 감소시킵니다.

소스 코드

http://boj.kr/dc1bb71636ce4fbb9bc7b25e239704f0

---

참고