[BaekJoon] 14502 연구소 :: monton

문제

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

풀이

dfs로 풀었는데 bfs도 가능할것 같다

dfs로 3개의 벽을 차례로 놓은 후 바이러스 퍼지는 것을 dfs로 다시 구현하여 남은 0이 몇개인지 구하면 된다

코드

#include <iostream>
 
using namespace std;
 
int N, M,ans;
int arr[9][9];
int visit[9][9];
int visit2[9][9];
int dir[4][2] = { {-1,0},{0,1},{1,0},{0,-1} };
 
void dfs(int x, int y) {
    if (x < 0 || x >= N || y < 0 || y >= M) return;
    if (visit2[x][y]||arr[x][y]==1) return;
    visit2[x][y] = 1;
 
    for (int i = 0; i < 4; i++) {
        dfs(x + dir[i][0], y + dir[i][1]);
    }
}
 
void init() {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            visit2[i][j] = 0;
        }
    }
}
 
void func(int x, int y,int cnt) {
    if (cnt == 3) {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (arr[i][j] == 2&&!visit2[i][j]) dfs(i,j);
            }
        }
 
        
        int num = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (!arr[i][j]&&!visit2[i][j]) num++;
            }
        }
 
        init();
        ans = ans > num ? ans : num;
        return;
    }
 
    for (int i = x; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (!arr[i][j]&&!visit[i][j]) {
                visit[i][j] =arr[i][j]= 1;
                func(i, j, cnt + 1);
                visit[i][j] = arr[i][j] = 0;
            }
        }
    }
}
 
int main() {
    cin >> N >> M;
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> arr[i][j];
        }
    }
    func(0, 0, 0);
    cout << ans;
 
}