연구소

코드

#include <cstdio>
#include <vector>
#include <queue>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <set>
#include <deque>
#include <numeric>
#define ll long long
#define ull unsigned long long
using namespace std;
// 06:37 ~ 07:10
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
int N,M,ans;
int board[10][10];
int cpy[10][10];
bool vis[10][10];
vector<pair<int,int>> virus;
vector<pair<int,int>> zero;
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> N >> M;
    for(int i=0;i<N;i++)
    {
        for(int j=0;j<M;j++)
        {
            cin >> board[i][j];
            if(board[i][j] == 2)
                virus.push_back({i,j});
            else if(board[i][j] == 0)
                zero.push_back({i,j});
        }
    }
    int ch[zero.size()];
    fill(ch, ch+zero.size(), 1);
    for(int i=0;i<3;i++) ch[i] = 0;
    do{
        queue<pair<int,int>> q;
        for(int i=0;i<N;i++)
        {
            fill(vis[i], vis[i]+M, false);
            for(int j=0;j<M;j++)
                cpy[i][j] = board[i][j];
        }
        for(int i=0;i<zero.size();i++)
            if(ch[i] == 0)
                cpy[zero[i].first][zero[i].second] = 1;
        for(int i=0;i<virus.size();i++)
        {
            vis[virus[i].first][virus[i].second] = true;
            q.push(virus[i]);
        }
        while(!q.empty())
        {
            auto cur = q.front(); q.pop();
            for(int dir=0;dir<4;dir++)
            {
                int ny = cur.first + dy[dir];
                int nx = cur.second + dx[dir];
                if(nx<0 or ny<0 or nx>=M or ny>=N) continue;
                if(vis[ny][nx] or cpy[ny][nx] == 1) continue;
                q.push({ny,nx});
                vis[ny][nx] = true;
                cpy[ny][nx] = 2;
            }
        }
        /* 안전영역 검사 */
        int cnt=0;
        for(int i=0;i<N;i++)
            for(int j=0;j<M;j++)
                if(cpy[i][j] == 0) cnt++;
        ans = max(ans, cnt);
    }while(next_permutation(ch, ch+zero.size()));
    cout << ans;
    return 0;
}

• 로직
  • next_permutation()으로 모든 '0' 좌표중 3개를 선택해서 '1'로 바꾸고 BFS를 실행
  • '0' 카운드하여 최대값 카운트

• next_permutation() 이 없으면?
  : 3-depth인 재귀를 통해 3개의 '0'좌표를 '1'로 바꾼 뒤 BFS 수행!