알고리즘을 다시 꾸준하게 공부중이다.
알고리즘을 공부하면서 알고리즘 문제를 많이 푸는것도 중요하지만 남한테 설명할 수 있을만큼 문제를 완전히 내 것으로 만드는것도 중요함을 느끼고 있다.
그래서 다시 열심히 블로그를 작성해볼까 한다.

백준 14502 연구소

이 문제는 DFS를 이용하여 풀었다.

이 문제는 경우에 따른 안전 영역의 개수를 구하는 문제이다.

0은 빈 칸, 1은 벽, 2는 바이러스이다.

1. 벽(1)을 랜덤으로 3개를 세운다. -> 벽을 세우고 또 다시 철수해야함 재귀 활용

static void DFS(int count) {
		if (count == 3) {
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < M; j++) {
					temp[i][j]=map[i][j];
				}
			}
            //바이러스 퍼뜨리기
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < M; j++) {
					if (temp[i][j] == 2) {
						virus(i, j);
					}
				}
			}
			result = Math.max(getScore(), result);
			return;
		}
        //벽을 세우는 부분을 DFS로
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (map[i][j] == 0) {
					map[i][j] = 1;
					count++;
					DFS(count);
					map[i][j] = 0;
					count--;
				}
			}
		}
	}

2. 바이러스(2)를 상하좌우로 퍼뜨린다. 벽(1)이 있으면 퍼지지 않는다.

	static void virus(int x,int y){
		for(int i=0;i<4;i++){
			int nx=x+dx[i];
			int ny=y+dy[i];
			if(nx>=0&&ny>=0&&nx<N&&ny<M){
				if(temp[nx][ny]==0){
					temp[nx][ny]=2;
					virus(nx,ny);
				}
			}

		}

	}

3. 안전구역을 구한다.

	static int getScore(){
		int score=0;
		for(int i=0;i<N;i++){
			for(int j=0;j<M;j++){
				if(temp[i][j]==0){
					score++;
				}
			}
		}
		return score;
	}

전체 코드

public class 연구소2 {
	static int N,M;
	static int[][] map;
	static int[][] temp;
	static int result=0;
	static int[] dx={-1,0,1,0};
	static int[] dy={0,-1,0,1};
	static void virus(int x,int y){
		for(int i=0;i<4;i++){
			int nx=x+dx[i];
			int ny=y+dy[i];
			if(nx>=0&&ny>=0&&nx<N&&ny<M){
				if(temp[nx][ny]==0){
					temp[nx][ny]=2;
					virus(nx,ny);
				}
			}

		}

	}
	static int getScore(){
		int score=0;
		for(int i=0;i<N;i++){
			for(int j=0;j<M;j++){
				if(temp[i][j]==0){
					score++;
				}
			}
		}
		return score;
	}
	static void DFS(int count) {
		if (count == 3) {
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < M; j++) {
					temp[i][j]=map[i][j];
				}
			}
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < M; j++) {
					if (temp[i][j] == 2) {
						virus(i, j);
					}
				}
			}
			result = Math.max(getScore(), result);
			return;
		}
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (map[i][j] == 0) {
					map[i][j] = 1;
					count++;
					DFS(count);
					map[i][j] = 0;
					count--;
				}
			}
		}
	}
	public static void main(String[] args) throws IOException {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=new StringTokenizer(br.readLine());

		N=Integer.parseInt(st.nextToken());
		M=Integer.parseInt(st.nextToken());
		map=new int[N][M];
		temp=new int[N][M];

		for(int i=0;i<N;i++){
			st=new StringTokenizer(br.readLine());
			for(int j=0;j<M;j++){
				map[i][j]=Integer.parseInt(st.nextToken());
			}
		}

		DFS(0);

		System.out.println(result);
	}
}