백준 14502 연구소 C++

 

 

1.문제 설명

연구소에서 바이러스가 유출되어 벽을 세워 전염을 막으려고 한다.

연구소는 N x M인 직사각형으로 되어있으며, 0은 빈칸, 1은 벽, 2는 바이러스가 있는 곳이다.

바이러스는 상하좌우 인접한 빈칸 모두 퍼져나가는데

빈칸에는 벽을 세워 전염을 막을 수 있다.

벽을 3개 세워서 얻을 수 있는 최대의 안전한 영역의 크기를 구하는 문제이다.

 

N은 3이상, M은 8이하의 크기로 주어진다.

 

벽은 dfs와 백트래킹을 통해 3개씩 세워주며 탐색하여 주고 

벽을 세운 맵을 bfs 함수에 전달하여

 

bfs함수로 바이러스를 퍼트리며 탐색하고

안전한 지역의 개수를 세서 max값으로 갱신하여 준다.