문제

• 
• 시간 제한: 2초
• 메모리 제한: 512MB

Problem Analysis

최댓값을 만드는 벽의 위치를 구하는 수식이나 논리는 따로 없다. 모든 경우를 조사해 보는 수밖에 없다. 이때, 각 경우에서, BFS로 바이러스를 퍼뜨려, 안전 영역의 수를 구하면 된다.

Algorithm

1. Brute Force로 다음에 가능한 경우를 찾는다
2. 해당 경우에 대해, BFS로 바이러스를 퍼뜨리고 남은 안전영역을 return 한다
3. 모든 경우를 확인할 때까지, 1로 돌아가 반복한다

Data Structure

• lab[N][M]: 연구소의 상황을 저장하기 위함
• virusQ: BFS를 통해 바이러스를 퍼뜨리기 위함

결과

Other

BruteForce에서 최악의 경우 시간복잡도는 O(C(NM, 3))이다. BFS에서는 O(5NM)이다.
따라서 최종 시간 복잡도는 O( (NM)^4 ) 이다.