연구소 C++ - 백준 14502

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

구현의 비중이 높은 bfs 문제이다.

먼저 이 문제는 0인 곳에 벽을 세우는 모든 경우의 수를 탐색해야 한다.

따라서 브루트포스와 bfs를 적절히 사용해야한다.

벽을 3개 세우는 경우를 모두 탐색해 그때 마다 0의 개수를 카운트 해준다.

이 과정이 백트래킹과 유사한 과정이어서 이미 진행되고 있는 배열의 수정이 불가하기 때문에 새로운 2차원 배열 spr을 사용해주었다.

그리고 2차원 배열을 복사하는 함수가 없어 따로 만들어주어 사용했다.

코드는 다음과 같다.

#include <bits/stdc++.h>
using namespace std;

int n,m;
int graph[8][8];
int tmp[8][8];
int safe_area=0;
int dx[]={1,-1,0,0};
int dy[]={0,0,1,-1};
int spr[8][8];

void tmpCopy(){
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			tmp[i][j]=graph[i][j];
		}
	}
}

void sprCopy(){
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			spr[i][j]=tmp[i][j];
		}
	}
}

void bfs(){
	queue<pair<int, int>> q;
	sprCopy();
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			if(spr[i][j]==2){
				q.push({i,j});
			}
		}
	}
	while(!q.empty()){
		int x=q.front().first;
		int y=q.front().second;
		q.pop();
		for(int i=0;i<4;i++){
			int nx=x+dx[i];
			int ny=y+dy[i];
			
			if(0<=nx && nx<n && 0<=ny && ny<m && spr[nx][ny]==0){
				spr[nx][ny]=2;
				q.push({nx,ny});
			}
		}
	}
	int cnt=0;
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			if(spr[i][j]==0){
				cnt++;
			}
		}
	}
	safe_area=max(safe_area,cnt);
}

void wall(int wallcnt){
	if(wallcnt==3){
		bfs();
		return;
	}
	
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			if(tmp[i][j]==0){
				tmp[i][j]=1;
				wall(wallcnt+1);
				tmp[i][j]=0;
			}
		}
	}
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> n >> m;
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			cin >> graph[i][j];
		}
	}
	
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			if(graph[i][j]==0){
				tmpCopy();
				tmp[i][j]=1;
				wall(1);
				tmp[i][j]=0;
			}
		}
	}
	cout << safe_area;
}