백준 14502번: 연구소

문제 설명

• 바이러스의 확산이 최소화되는 경우를 찾는 문제입니다.

접근법

• 모든 경우의 수를 직접 실행해봐야 정답을 알 수 있습니다.(완전탐색)
• 3개의 기둥을 선택해야 합니다.(조합)
• 바이러스가 퍼져나가는 걸 구현해야 합니다.(DFS or BFS)

pseudocode

main(){
	벽을 세울 수 있는 좌표를 can_block 리스트에 담습니다.
	조합()을 실행합니다.
}
조합(){
	if(3개의 기둥을 다 선택했다면){
    	3개의 기둥을 설치한 임의의 실험실 copyBoard를 만듭니다.
        copyBoard에서 2가 있는 곳을 기준으로 바이러스를 확산시킵니다.(DFS())
        바이러스를 모두 확산시킨 후 남은 0의 개수를 샙니다.
    }
    
}
DFS(int x, int y){ // 바이러스 확산
	(x,y)칸에 바이러스를 뿌립니다.
    for(위,아래,좌,우){
    	if(보드를 벗어나지 않았고, 해당 칸이 0이면(벽이 아니면)){
        	DFS(해당 칸);
        }
    }
}

정답

import java.util.*;

public class Main {
	static int N, M;
	static int[] dx = { 0, 1, 0, -1 };
	static int[] dy = { 1, 0, -1, 0 };
	static int max_score = Integer.MIN_VALUE;
	static int[][] board;
	static List<pos> can_block = new ArrayList<pos>();
	static int[] selected_num = new int[3];

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		M = sc.nextInt();
		board = new int[N][M];
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				int val = sc.nextInt();
				board[i][j] = val;
				if (val == 0)
					can_block.add(new pos(i, j));
			}
		}
		comb(0, 0);
		System.out.println(max_score);
	}
	// 조합
	public static void comb(int depth, int start) {
		if (depth == 3) {
        	// 복사본board를 만듭니다.
			int[][] copyBoard = new int[N][M];
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < M; j++) {
					copyBoard[i][j] = board[i][j];
				}
			}
            // 3개의 기둥을 copyBoard에 설치합니다.
			for (int i = 0; i < 3; i++) {
				pos block = can_block.get(selected_num[i]);
				copyBoard[block.x][block.y] = 1;
			}

			// 바이러스를 확산시킵니다.
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < M; j++) {
					if (copyBoard[i][j] == 2)
						DFS(i, j, copyBoard);
				}
			}
			
            // 바이러스가 모두 확산된 후 남은 안전지대를 카운트합니다.
			int score = 0;
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < M; j++) {
					if (copyBoard[i][j] == 0) score++;
				}
			}

			max_score = Math.max(max_score, score); // 안전지대의 개수가 많은 값이 최종 정답이 됩니다.
			return;
		}
		for (int i = start; i < can_block.size(); i++) {
			selected_num[depth] = i;
			comb(depth + 1, i + 1);
		}
	}

	public static void DFS(int x, int y, int[][] copyBoard) {
		copyBoard[x][y] = 2;
		for (int d = 0; d < 4; d++) {
			int nx = x + dx[d];
			int ny = y + dy[d];
			if (0 <= nx && nx < N && 0 <= ny && ny < M && copyBoard[nx][ny] == 0) {
				DFS(nx, ny, copyBoard);
			}
		}
	}

	static class pos {
		int x;
		int y;

		public pos(int x, int y) {
			super();
			this.x = x;
			this.y = y;
		}

		@Override
		public String toString() {
			return "pos [x=" + x + ", y=" + y + "]";
		}

	}
}