[BOJ 백준] 14502 연구소 - 자바

문제 접근 방법

1. 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갑니다. 이 조건을 토대로 저는 BFS라는 접근 방법을 떠올릴 수 있었습니다.

2. 벽의 개수는 3개이며, 꼭 3개를 세워야 합니다. 이 조건을 토대로 저는 놓을 수 있는 벽의 위치를 찾는 메서드 choiceLocation 함수를 구현하였습니다. 벽의 위치를 세울 수 있는 모든 위치의 경우의 수를 int[][] output에 인덱스 형태로 저장하였습니다.

 

문제 접근하며 어려웠던 점

1. 벽을 놓을 수 있는 3개의 위치를 지정하면 그때 BFS 함수를 호출하는 로직을 구현하는 과정에서 다른 경우의 수도 계산하기 위해서 초기화가 이루어져야 했습니다. 따라서, 저는 배열의 복사본을 만들어 복사본으로 bfs를 탐색하였습니다.

 

public class Main_14502 {
	
	static int N, M;
	static Queue<int[]> queue;
	private static int[][] maps;
	static int result;
	
	public static void main(String[] args) throws NumberFormatException, 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());

		maps = new int[N][M];
		queue = new LinkedList<>();
		result = 0;

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

		System.out.println(result);
	}

	//바이러스를 큐에 넣음
	static void getVirus(int[][] input) {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if(input[i][j] == 2) {
					queue.add(new int[] {i, j});
				}
			}
		}
	}
	
	//세울 수 있는 벽의 위치를 전부 구함
	static void choiceLocation(int[][] output, int cnt, boolean[][] checked) {
		if(cnt == 3) {
			int[][] copyMaps = new int[N][M];
			copyArray(maps, copyMaps);
			for (int i = 0; i < output.length; i++) {
				copyMaps[output[i][0]][output[i][1]] = 1;
			}
			getVirus(copyMaps);
			solve(copyMaps);
			return;
		}
		
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if(maps[i][j] == 0 && !checked[i][j]) {
					checked[i][j] = true;
					output[cnt] = new int[] {i, j};//벽의 위치 인덱스 저장
					choiceLocation(output, cnt+1,checked);
					checked[i][j] = false;					
				}
			}
		}
	}
	
	static void copyArray(int[][] original, int[][] copy) {
		for (int i = 0; i < N; i++) {
			System.arraycopy(original[i], 0, copy[i], 0, copy[i].length);	
		}
	}
	
	static int[][] dir = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };// 상하좌우

	static void solve(int[][] input) {
		boolean[][] visited = new boolean[N][M];

		while(!queue.isEmpty()) {
			int[] temp = queue.poll();
			int nowX = temp[0];
			int nowY = temp[1];
			
			visited[nowX][nowY] = true;
			
			for (int i = 0; i < dir.length; i++) {
				int nextX = nowX + dir[i][0];
				int nextY = nowY + dir[i][1];
				
				if(nextX < 0 || nextX >= N || nextY < 0 || nextY >= M) continue;
				if(visited[nextX][nextY]) continue;
				
				if(input[nextX][nextY] == 0) {
					input[nextX][nextY] = 2;
					queue.add(new int[] {nextX, nextY});
				}	
			}
		}
        
		result = Math.max(getCount(input), result);

	}
	
	
	static int getCount(int[][] input) {
		int cnt = 0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if(input[i][j] == 0) {
					cnt++;
				}
			}
		}
		return cnt;
	}
	
}