(C++) 백준 14502 연구소

N의 범위가 작아서 브루트포스로 풀었다. 다음과 같은 flow로 작성했다.

1. 벽 세개 선택해서 세우기
2. 벽을 세운 뒤 바이러스가 퍼졌을때 안전영역 구하기

벽 3개를 선택하는 방법이 처음에 생각이 안났는데;;
그냥 심플하게 미리 비어있는 지점들을 다 vector에 입력하고, vector값 중 세개를 조합으로 선택하는 식으로 작성했다. 풀땐 재귀로 풀었는데 다른풀이보니 3중 for문으로 푸는게 효율적인거같다. (https://www.acmicpc.net/source/38250385)

인근의 빈구역에 바이러스를 퍼뜨리는건 dfs를 사용했다.
처음에 조건을 잘못넣어서 디버깅만 한시간 했다 ㅠ (&&랑 || 주의...)
그리고 변수명 너무 헷갈리게 쓰는거같다.. 비슷하게 짠다고 짰는데 오히려 눈에 잘 안익어서 눈에 잘 보이도록 짜야겠다

#include <iostream>
#include <queue>
#include <vector>
#include <cstring>
using namespace std;


int map[10][10];
int tmp[10][10];
bool isVisited[10][10];
vector<pair<int, int>> blank;
vector<pair<int, int>> virus;
int N,M;
int ans;

const pair<int, int> dir[4] = {{0,1}, {0,-1}, {1,0},{-1,0}};


void makeWall(int prev, int cnt){

    if(cnt==3) {
        memset(isVisited, false, sizeof(isVisited));

        // copy map 
        for (int i = 0; i < N; i++)
            for (int j = 0; j < M; j++)
                tmp[i][j] = map[i][j];


        // spread virus
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (tmp[i][j] != 2 || isVisited[i][j]) continue;
                queue<pair<int, int> > q;
                q.push({i, j});

                while (!q.empty()) {

                    int tmpy = q.front().first;
                    int tmpx = q.front().second;
                    q.pop();
                    isVisited[tmpy][tmpx] = true;

                    for (int k = 0; k < 4; k++) {

                        int tmpyy = tmpy + dir[k].first;
                        int tmpxx = tmpx + dir[k].second;

                        if (tmpyy < 0 || tmpxx < 0 || tmpyy >= N || tmpxx >= M) continue;
                        if (!isVisited[tmpyy][tmpxx] && tmp[tmpyy][tmpxx] == 0) {
                            tmp[tmpyy][tmpxx] = 2;
                            q.push({tmpyy, tmpxx});
                        }
                    }
                }


            }
        }


        // count safe zone
        int ret = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (tmp[i][j] == 0) ret++;
            }
        }

        if (ret > ans) ans = ret;
        return ;
    }

/*
        cout<<"-----"<<'\n';
        for(int i=0; i<N; i++){
            for(int j=0; j<M; j++){
                cout<<tmp[i][j];
            }
            cout<<'\n';
        }*/



        if(prev == (int) blank.size()) return ;

        int newy = blank[prev].first;
        int newx = blank[prev].second;

        map[newy][newx]=1;
        makeWall(prev+1, cnt+1);
        map[newy][newx]=0;
        makeWall(prev+1, cnt);

        return ;
}




int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    cin>>N>>M;
    for(int i=0; i<N; i++){
        for(int j=0; j<M; j++){
            cin>>map[i][j];
            if(map[i][j]==0) blank.push_back({i,j});
        }
    }


    makeWall(0, 0);
    cout<<ans;

}