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

해결 방법

벽을 세우고 + 바이러스를 DFS/BFS로 전파한 다음 + 안전지대를 카운트 해주면 된다.

벽 세우기

벽은 재귀로 세웠다.

• 보드에 벽을 세우고 (board[i][j] = 1)
• 벽 개수를 추가하여 재귀호출 한 뒤
• 재귀호출을 마치면 보드를 원상복구 (board[i][j] = 0) 해준다.
• 이 때 만약 벽 세개를 다 세웠다면,
  바이러스를 전파하고 안전지대를 카운트하여 답을 최댓값으로 갱신한다.

바이러스 전파

• 입력을 받을 때 미리 바이러스의 위치를 vector에 담아둔다.
• bfs로 인해 보드가 바뀌었을 것이므로,
  bfs 전 원래 상태를 저장해두었다가 bfs가 끝나면 원래 보드 상태로 되돌려준다.
• vector안의 바이러스들을 시작점으로, 모두 BFS를 실행해주었다.
  이때 시간초과가 발생할 수 있는 풀이 / 그것을 개선한 풀이 두 가지가 있는데 다음과 같다.

시간초과 발생

//in wall function
for(int i = 0; i<virus.size(); i++)
	bfs(i);

이 코드를 벽을 세우는 과정 안에 넣게 되면, 바이러스 개수는 최대 10개이므로
기존 시간복잡도 x10 이기 때문에 시간초과가 날 것이라 생각했다,,
실제로 테스트케이스 3번 실행할 때 답이 너무 느리게 나와서 왜 그럴까 싶었는데 얘가 원인이었다.

시간초과 개선

void bfs(){
	queue<pii> q;
	
	for(int idx = 0; idx<virus.size(); idx++)
		q.push(virus[idx]);
    :
    (후략)
    :

벽을 세우는 함수에서는 bfs() 한번만 실행하도록 하고,
bfs에선 시작 전 미리 큐에 바이러스들을 다 넣어놓는 것이다!
이렇게 하면 시간초과를 피할 수 있다

소스 코드

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
using namespace std;
#define pii pair<int,int>

int board[9][9];
int N,M;
vector<pii> virus;
int ans = 0;
bool visited[9][9];

const int dx[] = {-1,1,0,0};
const int dy[] = {0,0,-1,1};

void print_board(){
	cout<<"\n";
	for(int i = 0; i<N; i++){
		for(int j = 0; j<M; j++){
			cout<<board[i][j]<<"\t";
		}
		cout<<"\n";
	}
}

bool in_board(int x, int y){
	return (0<=x && x<N && 0<=y && y<M);
}

void clear_visited(){
	for(int i = 0; i<N; i++){
		for(int j = 0; j<M; j++){
			visited[i][j] = false;
		}
	}
}

void bfs(){
	queue<pii> q;
	
	for(int idx = 0; idx<virus.size(); idx++)
		q.push(virus[idx]);
	while(!q.empty()){
		pii cur = q.front(); q.pop();
		board[cur.first][cur.second] = 2;
		visited[cur.first][cur.second] = true;
		
		for(int i = 0; i<4; i++){
			int nx = cur.first + dx[i];
			int ny = cur.second + dy[i];
			
			if(!in_board(nx,ny)) continue;
			if(board[nx][ny]) continue;
			if(visited[nx][ny]) continue;
				
			q.push({nx,ny});
		}
	}
}

int cnt_board(){
	int ret = 0;
	for(int i = 0; i<N; i++){
		for(int j = 0; j<M; j++){
			if(!board[i][j]) ret++;
		}
	}
	return ret;
}

void wall(int n){
	if(n == 3){
		//벽을 다 세운 경우
		int origin[9][9];
		memcpy(origin,board,sizeof(board));
		clear_visited();
		
		bfs();
		
		ans = max(ans,cnt_board());
		//print_board();
		
		memcpy(board,origin,sizeof(origin));
		return;
	}
	for(int i = 0; i<N; i++){
		for(int j = 0; j<M; j++){
			if(board[i][j] == 0){
				board[i][j] = 1;
				wall(n+1);
				board[i][j] = 0;
			}
		}
	}
}



int main(){
	ios_base::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});
		}
	}
	wall(0);
	cout<<ans;
}

제출 결과

시간초과가 정말 개선된건지 확인차 제출해봤다
역시나.. 느렸다