BOJ 14502 연구소

문제

인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다.

연구소는 크기가 N×M인 직사각형으로 나타낼 수 있으며, 직사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다. 

일부 칸은 바이러스가 존재하며, 이 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다. 새로 세울 수 있는 벽의 개수는 3개이며, 꼭 3개를 세워야 한다.

연구소의 지도가 주어졌을 때 얻을 수 있는 안전 영역 크기의 최댓값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. (3 ≤ N, M ≤ 8)

둘째 줄부터 N개의 줄에 지도의 모양이 주어진다. 0은 빈 칸, 1은 벽, 2는 바이러스가 있는 위치이다. 2의 개수는 2보다 크거나 같고, 10보다 작거나 같은 자연수이다.

빈 칸의 개수는 3개 이상이다.

출력

첫째 줄에 얻을 수 있는 안전 영역의 최대 크기를 출력한다.

내 풀이

백트래킹 방식

바이러스를 세는 부분은 다른 분의 풀이를 참고했다.

바이러스를 셀 때 나는 처음에 기존 array에 2를 채워넣었다가 모두 없애는 방식으로 했었는데, 그랬더니 recursion error가 났다. (물론 내 코드가 다른 방향에서 틀렸을 수도 있다.)

이렇게 기존 array를 변화시켜서 무언가를 세어야 하는 문제의 경우에는 새로운 array를 만들어서 그 array에 업데이트를 하며 세는 방식이 좋은 것 같다.

 

벽을 세 개 세우면 c를 초기화하고(초기화하지 않으면 잘못된 값으로 세 버린다) virus 감염 지역을 센 변수를 업데이트한다.

virus 감염 지역을 세는 함수는 재귀적으로 모든 방향에 대하여 그 방향이 아직 감염되지 않았고, 0이라면 res 변수에 +1 해나가는 방식으로 센다.

safe (벽이 아닌 지역을 미리 세어 저장해놓은 변수) 의 초기값은 -3인데, 벽을 세울 것을 감안한 숫자이다.

최종적으로 safe에서 virus 감염 지역이 최소가 되는 숫자를 뺀 값을 print한다.