[BOJ] #14502 연구소

시간 제한	메모리 제한	정답 비율
2 초	512 MB	54.624%

14502번: 연구소

문제

0 : 빈 칸 1 : 벽 2 : 바이러스

로 나타내며, 바이러스가 퍼저나가는 것을 막기위해 반드시 3개의 벽을 세워야 한다. 
이 때 0인 부분을 안전 영역이라하고 안전 영역 크기의 최댓값을 구하는 것이다.

처음 아이디어는 2를 기준으로 벽을 하나씩 세워볼까 했다가 어쨌든 모든 경우를 다 봐야하므로 0 인 칸들을 모두 탐색하여 벽을 세우는 방법을 생각했다.

3 ≤ n, m ≤ 8

해결

key point, 브루트 포스로 벽을 세울 수 있는 모든 곳에 벽을 세워둔 후 BFS로 바이러스를 퍼트린다.

1. 바이러스 위치를 virus 큐에 저장한다.
2. 반드시 벽을 3개 세워야 하므로 lab( cnt, r, c ) 함수를 통해 벽 3개를 세우는 모든 경우에 대해 조사한다.
3. 원래 배열에서 0인 곳에만 벽을 세울 수 있다. lab(cnt-1, nr, nc)
4. 원래 배열에서 0인 곳에는 벽을 세울 수 있기도하고 안세울 수도 있다. lab(cnt, nr, nc)
5. cnt가 0일 때 벽을 세개 모두 세웠으므로 바이러스를 퍼트린다 → BFS
6. 바이러스가 모두 퍼진 후 0의 개수를 세서 ans 와 비교하여 더 큰 값으로 갱신시킨다.

벽 3개를 세우는 모든 경우에 대해서 탐색한 후 최종적으로 갖게 되는 ans는 최적이 답이 된다.

 

해결에 도움된 testcase

3 4
0 2 1 0
0 1 1 2
0 0 1 0

3 4
Y 2 X Y
0 X X 2
0 0 X Y
출력: 3

 

if (r >= n) return;

현재 36번째 줄에 있는 문장이
lab함수 맨 위(9번째 줄)에 위치하고 있어서 예제를 실행시키면 답이 2가 출력되었다.

순서를 바꾸니 해결.

 

코드

메모리	시간
1984 KB	44 ms

#include <iostream>
#include <string.h>
#include <queue>
using namespace std;
typedef pair<int, int> p;
queue<p> virus;
int n, m, arr[10][10], dx[] = { 0,0,1,-1 }, dy[] = { 1,-1,0,0 }, chk[10][10], ans;
void lab(int cnt, int r, int c) {
    if (cnt == 0) {
        queue<p> vir = virus;
        // BFS 진행
        while (!vir.empty()) {
            p front = vir.front();
            int x = front.first, y = front.second;
            chk[x][y] = 1;
            vir.pop();
            for (int k = 0; k < 4; k++) {
                int nx = x + dx[k], ny = y + dy[k];
                if (nx < 0 || ny < 0 || nx >= n || ny >= m || arr[nx][ny] > 0 || chk[nx][ny]) continue;
                chk[nx][ny] = 1;
                vir.push({ nx, ny });
            }
        }
        // 0개수 세기
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (arr[i][j] == 0 && chk[i][j] == 0) cnt++;
            }
        }
        // ans 갱신
        ans = cnt > ans ? cnt : ans;
        memset(chk, 0, sizeof(chk));
        return;
    }
    if (r >= n) return;
    int nr = c + 1 >= m ? r + 1 : r;
    int nc = c + 1 >= m ? 0 : c + 1;
    if (arr[r][c] == 0) {
        arr[r][c] = 1;
        lab(cnt - 1, nr, nc);
        arr[r][c] = 0;
    }
    lab(cnt, nr, nc);
}
 
int main() {
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            scanf("%d", &arr[i][j]);
            if (arr[i][j] == 2) virus.push({ i,j });
        }
    }
    lab(3, 0, 0);
    printf("%d", ans);
    return 0;
}