✓

태그:

CLASS 4

벽을 어떻게 놓아야 바이러스가 잘 막히는지는 고민하지 않아도 됩니다…!!

풀이 비스무리한거 보기

바이러스가 유출된 연구소에 벽을 세워 가장 넓게 만들 수 있는 안전지대의 넓이를 구하는 문제입니다. 먼저 브루트 포스를 이용하여 벽을 3개 놓는 모든 경우를 찾고, 벽을 놓는 각 경우에 대해 DFS/BFS를 사용하여 바이러스가 퍼질 수 있는 위치를 찾으면 됩니다. 일단 제 취향으로는 재귀를 사용하여 벽을 놓는 경우를 찾고 BFS를 사용하여 바이러스가 퍼질 수 있는 영역을 찾는 게 좋습니다. 그리고 굳이 시간을 줄이자면 마지막으로 벽을 놓은 위치 이후의 칸에 대해서만 벽을 새로 놓는 경우를 탐색하면 조금 줄어듭니다. 이를 사용하여 각 경우에 대해 안전 지대의 넓이를 구하고, 그 중 가장 큰 값을 출력하면 됩니다.

브루트 포스를 사용해도 되는 이유는 격자의 크기가 매우 작기 때문입니다(8×8). 가능한 경우의 최대값이 ₆₄C₃=41664가지밖에 안됩니다.

소스 코드

언어	코드	시간	비고
C++	코드(Github) / 코드(백준)	2021-02-11 22:57:15

---