백준 문제 14502번 연구소 문제풀이 c++

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

14502번: 연구소

 

문제해석

이 문제를 쉽게 푸는법이 존재하나 솔직히 모르겠다.

그래서 어쩔 수 없이 다 해보는 방법밖에 떠오르지않았다.

N*M의 최대크기가 64라서 시간복잡도를 계산하니 아마 2초내에 푸는것이 가능할거 같았다.

무식하게 다 해보는거니까 특별한 아이디어는 없고.. 전체 배열중 벽을 세울 수 있는 좌표 3개를 백트래킹으로 선택하고

3개를 전부 선택했으면 너비우선탐색을 통해 바이러스를 퍼뜨리고 다 퍼졌으면 전체 탐색으로 안전영역의 개수를 세주었다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
bool inside(int ny,int nx);
void bfs();
void dfs(int size,int index);
vector < pair<int,int> > virus;
queue < pair<int,int> > q;
int dy[4]={0,0,1,-1};
int dx[4]={1,-1,0,0};
int a[8][8];
int b[8][8];
bool visited[8][8];
bool visited2[8][8];
int n,m;
int ans=0;
int main(){
    cout.tie(NULL);
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=0; i<n; i++)
    {
        for(int j=0; j<m; j++)
        {
            cin>>a[i][j];
            b[i][j]=a[i][j];
            if(a[i][j]==2)
            {
                virus.push_back({i,j});
            }
        }
    }
    dfs(0,0);
    cout<<ans;
}
bool inside(int ny,int nx){
    if(0<=ny&&ny<n&&0<=nx&&nx<m)
    {
        return true;
    }
    else
    {
        return false;
    }
}
void bfs(){
    for(int i=0; i<virus.size(); i++)
    {
        q.push(virus[i]);
    }
    while(!q.empty())
    {
        int cy=q.front().first;
        int cx=q.front().second;
        q.pop();
        for(int i=0; i<4; i++)
        {
            int ny=cy+dy[i];
            int nx=cx+dx[i];
            if(inside(ny,nx)&&a[ny][nx]==0&&visited[ny][nx]==0)
            {
                visited[ny][nx]=1;
                a[ny][nx]=a[cy][cx]+1;
                q.push({ny,nx});
            }
        }
    }
}
void dfs(int size,int index){
    if(size==3)
    {
        bfs();
        int cnt=0;
        for(int i=0; i<n; i++)
        {
            for(int j=0; j<m; j++)
            {
                if(a[i][j]==0)
                {
                    cnt++;
                }
                else if(a[i][j]>=3)
                {
                    a[i][j]=0;
                }
                visited[i][j]=0;
            }
        }
        ans=max(ans,cnt);
        return;
    }
    for(int i=index; i<n*m; i++)
    {
        if(a[i/m][i%m]==0&&visited2[i/m][i%m]==0)
        {
            visited2[i/m][i%m]=1;
            a[i/m][i%m]=-1;
            dfs(size+1,i);
            a[i/m][i%m]=0;
            visited2[i/m][i%m]=0;
        }
    }
}