백준 14502 연구소

1. 설계를 명확하게 합니다. (예제 3개 돌리기) 2. 경우의 수를 나열합니다 (자세히_ 3. 초기화 조건을 확인합니다. 4. 가지치기를 합니다.

/*
1. 설계 완벽하게 하기(예제 3개 돌리기)
2. 초기화 조건 확인하기
3. 경우의 수 나열하기
4. 가지치기

17:23 

1. 벽을 세우는 dfs 함수
2. 바이러스 퍼트리는 bfs 함수
3. 숫자 세는 함수
4. 맵 리셋하는 함수

*/
 
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
 
#define SIZE 9
int map[SIZE][SIZE];
int visit[SIZE][SIZE];
int safe_cnt;
int maxVal;
struct point {
    int x, y;
};
queue<point> que;
int N, M;
int x, y, nx, ny;
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
int map_store[SIZE][SIZE];
 
void problemIn() {
    cin >> N >> M;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> map[i][j];
        }
    }
}
 
void visit_init() {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            visit[i][j] = 0;
        }
    }
}
 
void copy_map(int(*a)[SIZE], int(*b)[SIZE]) {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            b[i][j] = a[i][j];
        }
    }
}
 
void bfs() {
    while (!que.empty()) {
        x = que.front().x;
        y = que.front().y;
        que.pop();
        for (int i = 0; i < 4; i++) {
            nx = x + dx[i];
            ny = y + dy[i];
            if (nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
            if (map[nx][ny] == 0 && visit[nx][ny] == 0) {
                visit[nx][ny] = 1;
                map[nx][ny] = 2;
                que.push({ nx,ny });
            }
        }
    }
}
 
void dfs(int depth, int startI) {
 
    if (depth == 3) {
        
        visit_init();
        copy_map(map, map_store); // 바이러스 퍼트리기 전에 저장
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (map[i][j] == 2) {
                    visit[i][j] = 1;
                    que.push({ i,j });
                    bfs();
                }
            }
        }
 
 
 
        // 안전 영역 갯수 세기
        safe_cnt = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (map[i][j] == 0) {
                    safe_cnt++;
                }
            }
        }
 
        copy_map(map_store, map); // 바이러스 퍼트리기 전으로 되돌림
        maxVal = max(maxVal, safe_cnt);
        return;
    }
 
    for (int i = startI; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (map[i][j] == 0) {
                map[i][j] = 1;
                dfs(depth + 1, i);
                map[i][j] = 0;
            }
        }
    }
}
 
 
void solve() {
    // 벽 3개 세우는 함수
    dfs(0, 0);
}
 
int main() {
    problemIn();
    solve();
    cout << maxVal << endl;
    return 0;
}