문제

BOJ 14502: 연구소 https://www.acmicpc.net/problem/14502

풀이

조건

• 벽 3개를 모두 써서 바이러스가 퍼지지 못하는 안전지대의 최대 넓이를 구하는 문제이다.
• 상, 하, 좌, 우 만 벽으로 막으면 바이러스가 퍼지지 못한다.

풀이 순서

• ArrayList에 벽을 세울 수 있는 좌표를 미리 넣어놓는다.
• 백트래킹을 이용해 벽 3개를 모두 세우는 경우를 구해 안전지대의 넓이를 구한다.
  • 종료 조건에 새로운 배열(newMap)을 Deep-Copy 한다.
  • newMap에서 BFS를 사용해 바이러스를 퍼트리고 안전지대의 넓이를 구한다.

코드

import java.util.*;
import java.io.*;

public class Main {
	
	static int N, M;
	static int[][] map;
	static int max; // 구할 답
	static ArrayList<Pos> list = new ArrayList<>(); // 벽 세울 수 있는 좌표 넣을 리스트
	static Pos[] arr; // 조합한 벽 세울 좌표 3개 넣을 배열
	static boolean[][] isChecked; // 백트래킹에 쓸 체크 배열
	
	static int[] dx = {0, 0, -1, 1};
	static int[] dy = {1, -1, 0, 0};
	
	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];
		
		
		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());
				// 벽 세울 수 있는 좌표를 미리 리스트에 넣어 놓음
				if(map[i][j] == 0) {
					list.add(new Pos(i, j));
				}
			}
		}
		
		isChecked = new boolean[N][M]; // 백트래킹에 쓸 체크 배열
		arr = new Pos[3]; // 조합한 벽 세울 좌표 3개 넣을 배열
		
		max = 0;
		
		bt(0, 0);
		
		System.out.println(max);
	}
	
	static void bt(int depth, int start) {
		/*
		 * depth: 종료조건에 사용할 파라미터
		 * start: 이미 조합에 넣은 좌표는 또 넣을 필요 없기 때문에 구분할 파라미터
		 */
		
		// 좌표 3개를 조합했다면 -> 종료
		if(depth == 3) {
			// 원본 배열은 수정하지 않기 위해 새로운 배열을 deep-copy함
			int[][] newMap = new int[N][M];
			for(int i=0; i<N; i++) {
				for(int j=0; j<M; j++) {
					newMap[i][j] = map[i][j];
				}
			}
			// 조합한 3개의 좌표에 1을 넣어 벽을 세움
			for(int i=0; i<3; i++) {
				int x = arr[i].x;
				int y = arr[i].y;
				
				newMap[x][y] = 1;
			}
			
			// bfs를 사용해 바이러스를 퍼트리고 이 때의 안전지대 넓이를 구함
			int num = bfs(newMap);
			// 구한 안전지대의 넓이 중 최댓값을 구함
			max = Math.max(max, num);
			
			return;
		}
		
		// 이미 조합에 사용한 좌표는 다시 조합하지 않기 위해 start 부터 리스트의 크기만큼 탐색하며 조합함
		for(int i=start; i<list.size(); i++) {
			int x = list.get(i).x;
			int y = list.get(i).y;
			// 중복 방지할 조건문
			if(!isChecked[x][y]) {
				isChecked[x][y] = true; // 조합한 좌표 체크 처리
				
				arr[depth] = new Pos(x, y); // 현재 depth를 인덱스로 하여 좌표를 조합함
				bt(depth + 1, i); // 재귀 호출
				
				isChecked[x][y] = false; // 다음 for문을 위해 좌표 체크 취소
			}
		}
	}
	
	static int bfs(int[][] newMap) {
		Queue<Pos> que = new LinkedList<>(); 
		boolean[][] isVisited = new boolean[N][M];
		int cnt = 0; // 안전 지대 넓이 구할 변수
		
		// 바이러스의 위치를 큐에 미리 다 넣음
		for(int i=0; i<N; i++) {
			for(int j=0; j<M; j++) {
				if(newMap[i][j] == 2) {
					que.add(new Pos(i, j));
				}
			}
		}
		
		while(!que.isEmpty()) {
			Pos p = que.poll();
			
			int curX = p.x;
			int curY = p.y;
			
			for(int t=0; t<4; t++) {
				int nx = curX + dx[t];
				int ny = curY + dy[t];
				
				if(nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
				
				// 바이러스가 퍼져 나갈 수 있는 좌표라면
				if(!isVisited[nx][ny] && newMap[nx][ny] == 0) {
					newMap[nx][ny] = 2; // 바이러스가 퍼진 자리는 2를 채움
					isVisited[nx][ny] = true;
					que.add(new Pos(nx, ny));
				}
			}
			
		}
		
		// 안전 지대 넓이 구하기
		for(int i=0; i<N; i++) {
			for(int j=0; j<M; j++) {
				if(newMap[i][j] == 0) {
					cnt++;
				}
			}
		}
		
		return cnt;
	}
	
	static class Pos{
		int x, y;
		
		Pos(int x, int y){
			this.x = x;
			this.y = y;
		}
	}
	
}

정리

• 원본 배열에 영향을 주지 않기 위해 deep-copy 를 해야한다는 것을 또 까먹어서 시간을 조금 낭비했다.