백준 14502 연구소

로직

• 벽을 3개 세운다 (완전탐색)
• 각 케이스 별로 안전 구역을 센다
• 그 중 가장 큰 것 return

기억 할 것

1. 벽 세우기 (dfs, 완전 탐색)

private static void buildWall(int depth, int start) {
		if(depth==3) {
			answer = Math.max(answer, bfs());
			return;
		}
		for(int i =start; i<N*M;i++) { // 2차원배열을 1차원으로 해결!
			int x = i%M;
			int y = i/M;
			if(tmp[y][x]==0) {
				tmp[y][x] = 1; // 방문 
				buildWall(depth+1,i+1); // 더 깊히 들어감
				tmp[y][x] = 0; // 백
			}
		}
		}
	

2. bfs로 바이러스 퍼뜨리기

private static int bfs() {
		Queue<Pos> q = new LinkedList<Pos>();
		int virus[][] = new int[N][M];
		boolean visited[][] = new boolean[N][M];
		for(int i = 0; i<N;i++) {
			for(int j = 0; j<M;j++) {
				virus[i][j] = tmp[i][j];
			}
		}
		
		for(int i = 0; i<N;i++) {
			for(int j = 0; j<M;j++) {
				if(virus[i][j] == 2) {
					q.offer(new Pos(j,i));
					visited[i][j] = true;
					while(!q.isEmpty()) {
						Pos k = q.poll();
						for(int a = 0; a<4;a++) {
							int nx = k.x + dx[a];
							int ny = k.y + dy[a];
							if(nx>=0&& ny >=0 && nx<M && ny<N&&virus[ny][nx] == 0) {
								virus[ny][nx] = 2;
								visited[ny][nx] = true;
								q.offer(new Pos(nx,ny));
							}
						}
					}
				}
			}
		}
		int cnt = 0;
		for(int i = 0; i<N;i++) {
			for(int j = 0; j<M; j++) {
				if(virus[i][j] == 0) {
					cnt++;
				}
			}
		}
		return cnt;
	}