[BOJ C++] 14502 연구소

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

14502번: 연구소

문제이해

직사각형 모양의 연구소가 있고, 연구소에 새로운 벽 3개를 설치하였을 때 바이러스가 퍼지지 않는 안전한 지역의 최대 갯수를 구하는 문제 였습니다. 중요한 점은 꼭 새로운 벽 3개는 필수적으로 설치를 해야한다는 점입니다.

단순히 모든 경우에 있어서 3개의 빈공간을 선택하여 벽을 설치하고, 바이스의 위치에서 bfs를 돈다고 했을 때 시간초과가 날까 걱정했지만 입출력 조건을 보고 가능하다 생각하게 되었습니다.

직사각형의 최대 크기는 8x8 = 64 였으며 벽 3개를 고르는 모든 경우의 수 64C3 = 41664 이며, 매번 모든 공간을 탐색한다고 하였을 때 최대 41664 x 64 = 2666496 으로 충분히 시간내에 가능하였습니다. (사실 크게 계산을 안해봐도 제한이 8이라는 것을 보았을 때 시간 제한은 걸리지 않을 것 같았습니다.)

 

입출력 조건

시간 제한은 2초, 직사각형의 최대 크기는 64 였고, 위의 식대로 시간초과가 나지는 않을 듯 하였습니다.

 

풀이

위 방식대로 문제를 해결하였으며 자세한 사항은 코드 내 주석을 참고해 주세요.