백준 - 연구소 (14502)

1. 문제

문제 링크

2. 풀이

2-1. 조건

1. 벽은 3개를 세울 수 있다.

2-2. 풀이

DFS + BFS가 결합된 문제입니다.
딱히 풀이랄 것도 없이 시키는 대로 구현하면 되는 문제입니다.

1. 백트래킹으로 모든 경우의 벽을 세웁니다.
2. 벽 3개를 세웠을 때 시뮬레이션을 진행할 map을 복사합니다.
3. BFS로 바이러스를 퍼뜨립니다.
4. 안전 구역을 셉니다.

DFS와 BFS의 기본기가 충분하다면 별 탈 없이 풀 수 있습니다.

3. 전체 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	static int N, M;
	static int[][] map;
	static int[] my = {-1,0,1,0}, mx = {0,1,0,-1};
	static Queue<int[]> q = new LinkedList<>();
	
	static int max(int depth) {
		// 3개의 벽을 세웠을 때
		if (depth == 3) {
			// 2. 시뮬레이션을 진행할 map을 복사합니다.
			int[][] simulation = new int[N][M];
			
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < M; j++) {
					simulation[i][j] = map[i][j];
					
					if (map[i][j] == 2) {
						q.add(new int[] {i, j});
					}
				}
			}
			
			// 3. BFS로 바이러스를 퍼뜨립니다.
			while (!q.isEmpty()) {
				int[] cur = q.poll();
				
				for (int i = 0; i < 4; i++) {
					int ny = cur[0] + my[i];
					int nx = cur[1] + mx[i];
					
					if (ny < 0 || ny >= N || nx < 0 || nx >= M) continue;
					
					if (simulation[ny][nx] != 0) continue;
					
					simulation[ny][nx] = 2;
					q.add(new int[] {ny, nx});
				}
			}
			
			int ret = 0;
			
			// 4. 안전 구역을 셉니다.
			for (int i =0; i < N; i++) {
				for (int j = 0; j < M; j++) {
					if (simulation[i][j] == 0) ret++;
				}
			}
			
			return ret;
		}
		
		int ret = 0;
		
		// 1. 백트래킹으로 모든 경우의 벽을 세웁니다.
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (map[i][j] == 0) {
					map[i][j] = 1;
					ret = Math.max(ret, max(depth + 1));
					map[i][j] = 0;
				}
			}
		}
		
		return ret;
	}
	
	public static void main(String[] args) throws Exception {
		StringTokenizer stk = new StringTokenizer(br.readLine());
		N = Integer.parseInt(stk.nextToken());
		M = Integer.parseInt(stk.nextToken());
		map = new int[N][M];
		
		for (int i = 0; i < N; i++) {
			stk = new StringTokenizer(br.readLine());
			for (int j = 0; j < M; j++) {
				map[i][j] = Integer.parseInt(stk.nextToken());
			}
		}
		
		bw.write(max(0) + "");
		bw.close();
	}
}